Сложность ДНК-последовательностей. Различные подходы и определения

Важной количественной характеристикой символьных последовательностей (текстов, строк) является сложность, отражающая на интуитивном уровне степень их “неслучайности”. Достаточно общий подход к оцениванию сложности сформулировал А.Н. Колмогоров. Он предложил измерять её длиной кратчайшего описания, по которому последовательность восстанавливается однозначно. Поскольку программы, гарантированно осуществляющей поиск кратчайшего описания, не существует, на практике для этой цели используют различные алгоритмические приближения, рассматриваемые в данной работе. Наряду с определениями сложности, предполагающими возможность восстановления последовательности по её описанию, рассмотрен и ряд мер, не обладающих указанным свойством. Основное внимание уделено не столько количественной оценке сложности, сколько выявлению и классификации структурных закономерностей, обусловивших конкретное её значение. Все они в той или иной форме сводятся к проявлениям повторности в самом широком смысле.
Рассматриваемые меры сложности можно условно разделить на статистические, учитывающие частоту встречаемости символов или коротких слов в тексте, “словарные”, оценивающие число всевозможных подслов в анализируемой последовательности (тексте) и “структурные”, основанные на выделении длинных повторяющихся фрагментов текста и установлении взаимосвязей между ними.
Большинство методов ориентировано на последовательности произвольной языковой природы. Особое внимание, уделяемое ДНК-последовательностям, отраженное в названии статьи, обусловлено значимостью объекта, проявлениями повторности разного типа и многочисленными примерами использования понятия сложности при решении задач классификации и эволюции различных биологических объектов. Значительный интерес представляют локальные структурные особенности, выявляемые в режиме скользящего окна в ДНК-последовательностях, поскольку зачастую зоны пониженной сложности в геномах различных организмов имеют отношение к регуляции основных генетических процессов.