Дано N строк, где последняя является нуклеотидной последовательностью длины L с CpG островками, а остальные содержат начальные и переходные вероятности для HMM. Эмиссионные вероятности считать равными log(10−30) или log(1) в зависимости от соответствия состояния наблюдаемому нуклеотиду. Требуется написать программу, находящую координаты CpG островков в соответствии с заданной HMM с помощью алгоритма Витерби.
Формат входного файла
Во входном файле содержатся N строк, где последняя содержит нуклеотидную последовательность длиной L с CpG островками, а остальные N−1 строк содержат начальные и переходные вероятности.
Вероятности выражены через натуральный логарифм и имеют формат stateprobability для начальных вероятностей и state1state2probability для переходных вероятностей, где state∈{A−,C−,G−,T−,A+,C+,G+,T+}.
Формат выходных данных
Выходной файл должен содержать координаты CpG островков, за начало отчета принять 1. Значения координат соответствуют первому и последнему символу островка.