ОПТИМАЛЬНАЯ СЕГМЕНТАЦИЯ НУКЛЕОТИДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ НА БЛОКИ С ОДНОРОДНЫМ СОСТАВОМ

Раменский В. Е., Макеев В. Ю., Ройтберг М. А., Туманян В. Г.
Институт молекулярной биологии РАН им. В. А. Энгельгардта, Москва; Институт математических проблем биологии РАН, 142292 Пущино
Рассматривается задача оптимальной сегментации заданной нуклеотидной последовательности на участки максимально однородные по составу. При этом решаются две основные трудности: (1) В некоторых случаях приходится проводить границы между двумя участками ДНК, содержащими все четыре буквы. (2) Необходимо рассматривать в рамках единого подхода блоки самой различной длины, от длинных, в десятки тысяч нуклеотидов, до самых коротких, состоящих из нескольких немногих букв. Задача решается в рамках статистического подхода, исходная последовательность сегментируется на блоки, в пределах которых последовательность считается случайной и бернуллиевской, с постоянными в пределах блока частотами встречаемости индивидуальных нуклеотидов. В случае коротких блоков простейшая оценка частоты встречаемости нуклеотидов дает завышенное значение для вероятности нуклеотида в случайной последовательности. В основе предлагаемого нами подхода лежит применение байесовских оценок для частот встречаемости нуклеотидов в пределах блоков и оптимизация по всевозможным позициям границ между блоками. Применение динамического программирования делает возможным эффективную оптимизацию и расчет реальных последовательностей длиной вплоть до десятков тысяч нуклеотидов в разумное время. Разработан алгоритм эффективного слияния блоков, близких по составу, с целью получения субоптимальных решений, отвечающих длинным, сравнительно однородным участкам ДНК. Алгоритм основан на расчете статистической суммы на множестве возможных границ. Предлагаемый подход позволяет естественным образом включить процедуры сегментации ДНК, построенные на основании анализа сложности последовательностей, но позволяет также рассматривать и очень короткие блоки.