Алгоритмы графиков в биоинформатике: выравнивание последовательностей и филогенетические деревья

Основополагающая роль графических алгоритмов в биоинформатике

Современная биоинформатика построена на способности сравнивать, выравнивать и выводить отношения из массивных биологических наборов данных. В основе этих задач лежит теория графов, раздел математики, который моделирует попарные отношения между объектами. Графовые алгоритмы обеспечивают вычислительную основу для двух краеугольных приложений: выравнивания последовательностей и построения филогенетических деревьев. Представляя биологические последовательности и их эволюционные расстояния в качестве узлов и краев, исследователи могут применять хорошо понятные методы обхода графов и оптимизации для решения проблем, которые в противном случае были бы трудноразрешимыми. В этой статье исследуется, как алгоритмы графов питают эти анализы, подробно исследуются основные методы и подчеркивается их более широкое значение в современной биологии.

Графики — естественное представление биологических данных. Последовательность ДНК можно рассматривать как путь через граф нуклеотидов; выравнивание между двумя последовательностями соответствует пути через граф редактирования; набор видов с генетическими расстояниями образует взвешенный граф, где минимальное дерево протяженности или кратчайшие пути дают эволюционные истории. Универсальность алгоритмов графов делает их незаменимыми в биоинформатике, позволяя все от сборки генома до предсказания структуры белка. Ниже мы погружаемся в глубокое выравнивание последовательностей и филогенетические деревья, две области, где методы графа оказали самое глубокое влияние.

Выравнивание последовательностей через графические представления

Выравнивание последовательностей — это процесс организации последовательностей ДНК, РНК или белка для идентификации областей сходства, которые могут указывать на функциональные, структурные или эволюционные отношения. Алгоритмы графов являются центральными как для выравнивания попарно, так и для выравнивания последовательности. Классические подходы динамического программирования для выравнивания могут быть переосмыслены как проблемы с кратчайшим путем в направленных ациклических графах, а современные выравниватели часто используют индексы на основе графов для скорости. Понимание этих методов требует взгляда на лежащие в основе модели графов.

Модель Edit Graph

Рассмотрим две последовательности, A длины и B длины n. График редактирования представляет собой направленный ациклический граф с (m+1) × (n+1) узлами. Каждый узел представляет собой возможные операции: диагональный край от (i-1, j-1) до (i, j) подразумевает сопоставление или замену символов в этих положениях; горизонтальный край от (i-1, j) до (i, j) соответствует вставке в первую последовательность (или делеции во вторую); вертикальный край от (i, j-1) до (i, j) представляет собой делецию в первой последовательности. Каждому краю присваивается вес, основанный на схеме подсчета очков (матч, несоответствие, штраф за разрыв). Оптимальным выравниванием является путь от начального узла (0,0) до конечного узла (m,

Эта формулировка графа непосредственно приводит к алгоритму Нидлмана-Вунша для глобального выравнивания и алгоритму Смита-Ватермана для локального выравнивания. Оба являются алгоритмами динамического программирования, которые решают оптимальную задачу пути в O(mn) времени. Перспектива графа уточняет, почему эти алгоритмы работают: они исследуют все возможные выравнивания (пути), но избегают пересчета субпатов с использованием мемуализации. Это по существу алгоритм кратчайших путей на сеточном графе.

Needleman-Wunsch: глобальное выравнивание

Алгоритм Нидлмана-Вунша находит оптимальное глобальное выравнивание двух последовательностей. Он строит матрицу скоринга (эквивалентную вычислительным расстояниям в графе редактирования), а затем прослеживает через матрицу, чтобы восстановить выравнивание. В терминах графа алгоритм вычисляет максимальный весовой путь от источника к погружению в графе редактирования. Рецидивы:

F(i, j) = max(F(i-1, j-1) + score(A[i], B[j]), F(i-1, j) + gap, F(i, j-1) + gap )

с соответствующими граничными условиями. Это классический пример динамического программирования на графике. Алгоритм до сих пор широко используется сегодня для выравнивания тесно связанных последовательностей, где ожидается глобальное сходство. Он формирует основу для многих инструментов сравнения последовательностей, в том числе используемых в выравнивании целого генома.

Смит-Вотерман: локальное выравнивание

Во многих биологических контекстах последовательности имеют только частичное сходство. Например, белковые домены могут сохраняться, в то время как другие области не связаны. Алгоритм Смита-Уотермана адаптирует подход редактирования графа для поиска наилучшего локального выравнивания. Он изменяет рецидив, чтобы позволить счету сброситься до нуля, если он становится отрицательным, эффективно ища субпат с высоким весом, который не обязательно охватывает весь граф. В терминах графа он находит субпат с самым высоким показателем между любыми двумя узлами. Этот алгоритм более чувствителен для обнаружения консервативных мотивов и является основой таких инструментов, как BLAST (хотя BLAST использует эвристические ускорения).

Сила алгоритма Смита-Уотермана заключается в его способности исследовать все возможные локальные выравнивания при сохранении той же сложности в худшем случае O(mn). Современные реализации используют векторизованные инструкции и ускорение GPU для обработки миллиардов пар оснований. Представление графа остается наиболее интуитивным способом понять, почему алгоритм возвращает пару сегментов с самым высоким показателем.

За пределами парной выравнивания: выравнивание множественных последовательностей и индексация на основе графика

При выравнивании трех или более последовательностей алгоритмы графов становятся еще более критичными. Многопорядковое выравнивание (MSA) может быть формализовано как задача с наименьшим траекторием в высокоразмерном графе сетки, но пространство состояний растет экспоненциально с числом последовательностей. Поэтому прогрессивные и основанные на консистенции методы полагаются на направляющие деревья (сами графовые структуры) и выравнивания профилей. Такие инструменты, как Clustal Omega, используют диаграммы расстояний для построения деревьев, а затем выполняют попарные выравнивания вдоль дерева.

Современные выравнивающие геномы структуры также используют графовые структуры данных для индексирования целых геномов. Например, преобразование Burrows-Wheeler с FM-индексом строит график отношений суффикса-префикса в геноме, что позволяет быстро сопоставлять шаблоны. Эти индексы можно рассматривать как компактные де-бруйнские графы или деревья суффикса. Затем шаг выравнивания становится поиском пути в графе, который захватывает как эталонный геном, так и известные вариации. Этот подход используется выравнивателями, такими как BWA-MEM и обеспечивает скорость, необходимую для крупномасштабной геномики популяции.

Филогенетическая конструкция деревьев: алгоритмы графов для эволюционного вывода

Филогенетические деревья изображают эволюционные отношения между видами или генами на основе генетических данных. Ввод обычно представляет собой множественную выравнивание последовательностей или матрицу расстояний, полученную из нее. Цель состоит в том, чтобы построить дерево, длина ветвей которого представляет собой величину эволюционных изменений. Алгоритмы графов используются почти на каждом этапе, от вычисления расстояний до поиска оптимальных топологий деревьев.

Методы дистанционного управления: UPGMA и Neighbor-Joining

Методы, основанные на расстоянии, начинаются с матрицы попарно-генетических расстояний. Эту матрицу можно рассматривать как полный граф, где каждый узел является видом, а каждый вес края — эволюционное расстояние. Проблема построения дерева становится одной из задач нахождения дерева, которое наилучшим образом соответствует этим расстояниям, часто путем кластеризации или минимизации общей длины ветви.

UPGMA (Unweighted Pair Group Method with Arithmetic Mean) — самый простой алгоритм кластеризации.] Он строит корневое дерево путем итеративного слияния двух ближайших узлов (на основе матрицы расстояний) и пересчитывает расстояния между новым кластером и оставшимися узлами как среднее арифметическое отдельных расстояний. В графовом выражении UPGMA представляет собой иерархический алгоритм кластеризации, который работает на взвешенном полном графе. Он производит дерево, которое является ультраметрическим, то есть все листья равноудалены от корня. UPGMA хорошо работает для тесно связанных последовательностей с постоянными молекулярными часами. Алгоритм работает во времени O(n3), где n — число таксонов, но может быть оптимизирован до O(n2) с использованием очередей приоритета.

Сосед-присоединение (NJ) является более гибким методом, который не предполагает постоянной скорости эволюции.] Он также работает на матрице расстояний и строит некорневое дерево. Алгоритм идентифицирует пары таксонов, которые минимизируют общую длину ветви (сумма всех длин ветвей в дереве.]минимальная эволюция, концепция, уходящая корнями в теорию графов. NJ использует специфический критерий под названием Q-статистика для выбора пары соседей для объединения. Алгоритм неоднократно находит пару (i, j) которая минимизирует:
] Q(i,j) = (n-2)*d(i,j) — Σ d(i,k) — Σ d(j,k)
, где суммы находятся над всеми другими таксонами k. Это графо-теоретическая мера, которая идентифицирует пару

Методы, основанные на характере: максимальная ПАРИЗМИЯ и максимальная вероятность

Методы, основанные на символах, используют выровненные последовательности непосредственно, а не расстояния. Они оценивают топологии деревьев-кандидатов и выбирают тот, который лучше всего объясняет наблюдаемые символы в рамках данной модели. Эти методы также полагаются на алгоритмы графов, особенно для поиска деревьев.

Максимальная парсимония ищет дерево, которое требует наименьших эволюционных изменений (замен). Это, по сути, проблема дерева Штайнера на пространстве состояний символов, которая является NP-твердой. Эвристические стратегии поиска, такие как обмен ближайшими соседями (NNI), обрезка и пересадка деревьев (SPR), и сечение и пересоединение деревьев (TBR), являются операциями на основе графов, которые исследуют пространство дерева. Эти движения изменяют топологию деревьев путем перегруппировки краев, и алгоритм поиска использует локальный оптимум для руководства исследованием. Оценка парсимонии для каждого дерева эффективно вычисляется с помощью алгоритма Fitch, который пересекает граф дерева сверху вниз, чтобы подсчитать изменения символов.

Максимальная вероятность (ML) является наиболее статистически строгим подходом. Он использует вероятностную модель эволюции (например, модель общего времени-перевернутого) для вычисления вероятности данных, данных о длине дерева и ветви. ML также требует поиска обширного пространства дерева, а алгоритмы графов необходимы как для поиска, так и для вычисления вероятности. Современные программы ML, такие как RAxML и IQ-TREE, используют сложные методы оптимизации на основе графов, включая симулируемое отжига и восхождение на холм на графике дерева. Они также используют библиотеку филогенетических вероятностей , которая использует разреженные матричные операции и оптимизацию длины ветви с помощью метода Ньютона, все подкреплены представлениями графов.