Граф последовательности

Граф последовательностей , также называемый графом выравнивания , графом точек останова или графом смежности, представляет собой двунаправленные графы, используемые в сравнительной геномике . Структура состоит из нескольких графов или геномов с рядом ребер и вершин, представленных как смежности между сегментами генома . и сегменты ДНК соответственно. Обход связного компонента сегментов и ребер смежности (называемого нитью ) дает последовательность, которая обычно представляет геном или часть генома. Сегменты можно рассматривать как блоки синтении , где края определяют, как расположить эти блоки в конкретном геноме, а маркировка ребер смежности представляет основания, которые не содержатся в блоках синтении.

Строительство

Прежде чем построить граф последовательности, должно быть как минимум два генома, представленных в виде ориентированных графов с ребрами в виде нитей (ребер смежности) и вершинами в виде сегментов ДНК. Геномы должны быть помечены P и Q, а граф последовательности помечен как BreakpointGraph( P, Q ).

Направленные вершины Q и их ребра располагаются в порядке P. После завершения ребра Q снова соединяются со своими исходными вершинами. После того, как все ребра сопоставлены, направления вершин удаляются, и вместо этого каждая вершина помечается как v. ^час (голова вершины) и v ^т (вершина хвоста).

Сходство между геномами выражается количеством циклов (независимых систем) в графе последовательности. Число циклов равно тактам (P, Q). Максимально возможное количество циклов равно количеству вершин в графе последовательности.

Пример

Пример рисунка.

При получении геномов P (+a +b -c) и Q (+a +b -c), Q следует выровнять так, чтобы он соответствовал направлениям ребер (красного цвета) P. Вершины следует переименовать из a, b, c в a. ^час а ^т , б ^час б ^т , с ^час с ^т и ребра P и Q должны быть соединены со своими исходными вершинами (ребра P = черные, ребра Q = зеленые). Удалите направляющие края (красные). Количество циклов в G(P, Q) равно 1, а максимально возможное — 3.

Приложения

Реконструкция геномов предков

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

Множественное выравнивание последовательностей

Графы последовательностей можно использовать для представления множественных выравниваний последовательностей с добавлением нового типа ребер, представляющих гомологию между сегментами. Для набора геномов можно создать ациклический граф точек останова с потоком для каждого генома. На два сегмента $(a,b)$ и $(c,d)$, где $a$, $b$, $c$, и $d$ представляют конечные точки двух сегментов, ребра гомологии могут быть созданы из $a$ к $c$ и $b$ к $d$ или из $a$ к $d$ и $b$ к $c$ - представляющие две возможные ориентации гомологии. Преимущество представления множественного выравнивания последовательностей таким способом заключается в том, что можно включать инверсии и другие структурные перестановки, которые недопустимы в матричном представлении.

Представление вариаций

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