Русская версия English version   
Том 15   Выпуск 2   Год 2020
Сложность ДНК-последовательностей. Различные подходы и определения

Гусев В.Д., Мирошниченко Л.А.

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

 

Содержание Оригинальная статья
Мат. биол. и биоинф.
2020;15(2):313-337
doi: 10.17537/2020.15.313
опубликована на рус. яз.

Аннотация (рус.)
Аннотация (англ.)
Полный текст (рус., pdf)
Список литературы

 

  Copyright ИМПБ РАН © 2005-2022