Введение

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

Определение

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

Выровнение последовательности

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

Метод матрицы расстояний

Метод расстояния измеряет минимальное количество операций вставки, удаления и замены символов, необходимых для преобразования одной последовательности u в другую последовательность v при работе с парой строк. Вычисление расстояния редактирования может быть основано на динамическом программировании, и его сложность составляет O(|u|×|v|), где |u| и |v| – длины последовательностей u и v соответственно. Эффективная оценка расстояния редактирования важна, поскольку метод расстояния является базовым принципом в вычислительной биологии. Для функций наследственных свойств можно использовать "симметризацию". Ввиду использования ряда функций для вычисления расстояния редактирования, различные функции могут давать разные результаты. Поиск оптимальной функции расстояния редактирования имеет решающее значение для задачи выравнивания деревьев.

Проблема выравнивания деревьев

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

Стратегия комбинаторной оптимизации

Комбинаторная оптимизация – эффективная стратегия для решения задач MSA. Основная идея комбинаторной оптимизации заключается в преобразовании выравнивания множественных последовательностей в выравнивание пар последовательностей для решения этой задачи. В зависимости от используемой стратегии преобразования, комбинаторная оптимизация подразделяется на алгоритм выравнивания по дереву и алгоритм звездного выравнивания. Для заданного набора множественных последовательностей ={, , }, необходимо найти эволюционное дерево с n листовыми узлами, устанавливающее взаимно однозначное соответствие между этим деревом и набором последовательностей. Назначая последовательности внутренним узлам эволюционного дерева, мы вычисляем суммарный балл для каждого ребра, а сумма баллов всех ребер определяет балл эволюционного дерева. Цель выравнивания по дереву – найти такое назначение последовательностей, которое максимизирует общий балл, и получить окончательный результат выравнивания на основе эволюционного дерева и назначенных последовательностей его узлов. Звездное выравнивание можно рассматривать как частный случай выравнивания по дереву, когда эволюционное дерево имеет только один внутренний узел и n листовых узлов. Последовательность, назначенная внутреннему узлу, называется основной (или корневой) последовательностью.

Теория дерева ключевых слов и алгоритм поиска Aho-Corasick

Когда комбинаторная стратегия оптимизации используется для преобразования выравнивания множественных последовательностей в выравнивание пар последовательностей, основная проблема меняется с "Как повысить эффективность выравнивания множественных последовательностей" на "Как повысить эффективность выравнивания пар последовательностей". Теория дерева ключевых слов и алгоритм поиска Aho-Corasick являются эффективным подходом к решению проблемы выравнивания последовательностей попарно. Цель объединения теории дерева ключевых слов и алгоритма поиска Aho-Corasick заключается в решении следующей задачи: для заданной длинной строки T и множества коротких строк S = {s₁, s₂, ..., s₂} (z∈N, z>1), найти все вхождения строк из S в T. Для этого используется дерево ключевых слов, построенное на основе множества S, и выполняется поиск в T с использованием этого дерева ключевых слов посредством алгоритма Aho-Corasick. Общая временная сложность использования этого метода для нахождения всех вхождений строк из S в T равна O(|T| + |S| + Σ|sᵢ|), где |T| – длина строки T, |S| – сумма длин всех строк из S, а Σ|sᵢ| – сумма количества вхождений всех строк из S в T.

Теория дерева ключевых слов

Дерево ключевых слов множества ={,, , } (z∈N, z>1) является корневым деревом, корень которого обозначен K, и это дерево ключевых слов удовлетворяет следующим условиям: (1): Каждое ребро однозначно обозначает одну букву. (2): Любые два исходящих из одного узла ребра соответствуют разным буквам. (3) Каждый образец (i=1, 2, ..., z) соответствует узлу , и путь от корня K до узла точно соответствует строке . Для каждого листового узла этого K-дерева, он соответствует одному из определенных образцов множества . обозначает строку, соединяющую корневой узел с узлом , и используется для представления длины самого длинного суффикса (который также является префиксом одного из образцов в множестве). Этот префикс ищется из корневого узла в дереве ключевых слов, и последний узел, обозначенный , определяется по завершении поиска. Например, множество ={potato, tattoo, theater, other}, и дерево ключевых слов показано справа. В этом примере, если =potat, то =|tat|=3, и ссылка отказа узла показана на рисунке. Установление ссылки отказа является ключевым для улучшения временной сложности алгоритма Aho-Corasick. Оно позволяет сократить исходное полиномиальное время поиска до линейного. Таким образом, ядро теории дерева ключевых слов заключается в нахождении всех ссылок отказа (что также означает нахождение всех s) дерева ключевых слов за линейное время. Предполагается, что для каждого узла, расстояние от которого до корневого узла не превышает , может быть найдено. Затем можно найти для узла, расстояние от которого до корневого узла равно +1. Его родительский узел – , а буква, представленная узлом и , равна . (1): Если следующая буква узла – , то другим узлом этого ребра можно установить , и =. (2): Если при поиске по всем ребрам между и его дочерними узлами не найдено ни одной буквы, является суффиксом плюс . Поскольку этот суффикс соответствует строке, начинающейся с корневого узла (аналогично префиксу), после можно обнаружить или не обнаружить. Если не обнаружено, этот процесс продолжается до тех пор, пока не будет найден или корневой узел.

Алгоритм поиска Aho-Corasick

После установления всех связей отказа в дереве ключевых слов алгоритм поиска Aho-Corasick используется для нахождения местоположений всех (i = 1, 2, ..., z) за линейное время. На этом этапе временная сложность составляет O(m+k).

Другие стратегии

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

Эвристический алгоритм

Как правило, эвристические алгоритмы опираются на итеративную стратегию, а именно на методы сравнения, оптимизирующие результаты множественного выравнивания последовательностей посредством итеративного процесса. Дэви М. предложил использовать алгоритм оптимизации роем частиц для решения задачи множественного выравнивания последовательностей; Икеда Такахиро предложил эвристический алгоритм, основанный на алгоритме поиска A*; Э. Бирни впервые предложил использовать скрытую марковскую модель для решения задачи множественного выравнивания последовательностей; и многие другие биологи используют генетический алгоритм для её решения. Все эти алгоритмы, как правило, устойчивы и нечувствительны к числу последовательностей, но они также имеют свои недостатки. Например, результаты, полученные с помощью алгоритма оптимизации роем частиц, нестабильны и зависят от выбора случайных чисел, время работы алгоритма поиска A* слишком велико, а генетический алгоритм склонен застревать в локальном оптимуме.

График выравнивания по дереву

Грубо говоря, граф выравнивания деревьев предназначен для объединения деревьев в граф и последующего их синтеза для получения статистических данных. В биологии графы выравнивания деревьев (TAG) используются для устранения эволюционных конфликтов или перекрывающихся таксонов из наборов деревьев, а затем могут быть использованы для изучения неопределенностей и противоречий. Интегрируя методы выравнивания, синтеза и анализа, TAG стремится разрешить противоречивые взаимосвязи и частичные перекрытия таксономических групп, полученные из широкого спектра последовательностей. Кроме того, граф выравнивания деревьев является основой для построения супердеревьев и операций прививки, успешно применявшихся Берри для конструирования супердеревьев. Поскольку преобразование деревьев в граф сохраняет общие узлы и связи из исходных деревьев, TAG также позволяет восстанавливать оригинальные исходные деревья для дальнейшего анализа. TAG представляет собой объединение набора выровненных деревьев. Он способен хранить противоречивые гипотезы об эволюционных взаимосвязях и синтезировать исходные деревья для разработки эволюционных гипотез. Таким образом, это базовый метод для решения других задач выравнивания.