Задача F. Поиск CpG островков с помощью HMM

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

Условие

Дано N строк, где последняя является нуклеотидной последовательностью длины L с CpG островками, а остальные содержат начальные и переходные вероятности для HMM. Эмиссионные вероятности считать равными log(10 − 30) или log(1) в зависимости от соответствия состояния наблюдаемому нуклеотиду. Требуется написать программу, находящую координаты CpG островков в соответствии с заданной HMM с помощью алгоритма Витерби.

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

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

Вероятности выражены через натуральный логарифм и имеют формат state probability для начальных вероятностей и state 1 state 2 probability для переходных вероятностей, где state ∈ {A − , C − , G − , T − , A + , C + , G + , T + }.

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

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

Ограничения

C = 73

L < 100000.

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

Входной файл (input.txt) Стандартный выход
1
A- -1.5432280925
C- -1.2610374051
G- -1.3076859937
T- -1.4589003294
A+ -80.3306836858
C+ -80.3306836858
G+ -80.3306836858
T+ -80.3306836858
A- A- -1.3887851737
A- C- -1.4892913109
A- G- -1.0716151683
A- T- -1.702929469
A- A+ -78.7875162711
A- C+ -7.7640533322
A- G+ -78.7875162711
A- T+ -78.7875162711
C- A- -1.3249755321
C- C- -1.0620420215
C- G- -2.2855263362
C- T- -1.250203786
C- A+ -79.06969204
C- C+ -8.3827013377
C- G+ -79.06969204
C- T+ -79.06969204
G- A- -1.5733254273
G- C- -1.3248409469
G- G- -1.0813114769
G- T- -1.6749677516
G- A+ -79.0230456365
G- C+ -8.1537333775
G- G+ -79.0230456365
G- T+ -79.0230456365
T- A- -2.082681587
T- C- -1.2714529969
T- G- -1.1105065043
T- T- -1.3264377255
T- A+ -78.8717833564
T- C+ -9.101083386
T- G+ -78.8717833564
T- T+ -78.8717833564
A+ A- -76.1898802345
A+ C- -76.1898802345
A+ G- -76.1898802345
A+ T- -76.1898802345
A+ A+ -1.7991214657
A+ C+ -1.1461807056
A+ G+ -0.9199649552
A+ T+ -2.1425141451
C+ A- -77.0184925521
C+ C- -77.0184925521
C+ G- -77.0184925521
C+ T- -77.0184925521
C+ A+ -1.6419905155
C+ C+ -0.9939637702
C+ G+ -1.4306814218
C+ T+ -1.6255817608
G+ A- -7.139660336
G+ C- -5.8868973675
G+ G- -5.6355829392
G+ T- -7.139660336
G+ A+ -1.8589979047
G+ C+ -1.0700780096
G+ G+ -1.0946550219
G+ T+ -1.8438460996
T+ A- -76.2667205282
T+ C- -76.2667205282
T+ G- -76.2667205282
T+ T- -76.2667205282
T+ A+ -2.7348204422
T+ C+ -0.9866322212
T+ G+ -0.9430609729
T+ T+ -1.7598221095
ATCGCGCGCGCGCGCGCGCGCGCGCG
3 26

0.090s 0.017s 15