Задача E. Оценка параметров HMM

Автор:Бойко   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:150 Мб
Выходной файл:Стандартный выход  

Условие

Дано C строк, где последняя является нуклеотидной последовательностью длины L с CpG островками, а остальные содержат координаты островков в последовательности. Требуется написать программу, расcчитывающую по этим данным начальные и переходные вероятности для 8 состояний — 4 нуклеотида c "-" или "+" состояниями. "+" соответствует нуклеотидам в CpG островке. Псевдокаунт в числителе для каждого состояния принять равным 10 − 30, в знаменателе — 1. То есть переходная вероятность для С+G+ будет aC + G +  = CC + G +  + 10 − 30CC + N + 1.

A начальная вероятность для G- будет a0G −  = CG −  + 10 − 30CN −  + 1.

Где N − ∈ {A − , C − , G − , T − } и N ∈ {A − , C − , G − , T − , A + , C + , G + , T + }.

Формат входного файла

Во входном файле содержатся C строк. Последняя содержит нуклеотидную последовательность длины L, а первые C − 1 строк содержат координаты CpG островков. Отсчет идет с 1, координаты включают первый и последний символ островка.

Формат выходных данных

Выходной файл должен содержать 68 строк, сначала начальные вероятности для каждого state, где state ∈ {A − , C − , G − , T − }, затем переходные вероятности для каждого state1 − state2, где state ∈ {A − , C − , G − , T − , A + , C + , G + , T + }. Порядок вывода вероятности лексиграфический, в соответствии с порядком в state.

При расчетах вероятности выражаем в натуральном логарифме и округляем до 5-го знака после запятой.

Ограничения

C < 12

L < 100000.

Примеры тестов

Входной файл (input.txt) Стандартный выход
1
3 26
ATCGCGCGCGCGCGCGCGCGCGCGCG
-1.09861
-70.17617
-70.17617
-1.09861
-69.7707
-69.7707
-69.7707
-0.69315
-69.7707
-69.7707
-69.7707
-69.7707
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.7707
-69.7707
-69.7707
-69.7707
-69.7707
-0.69315
-69.7707
-69.7707
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-71.6425
-71.6425
-71.6425
-71.6425
-71.6425
-71.6425
-0.08004
-71.6425
-71.56246
-71.56246
-71.56246
-71.56246
-71.56246
-0.08701
-71.56246
-71.56246
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755
-69.07755

0.072s 0.014s 15