Анализ последовательности без выравнивания

В биоинформатике для данных о молекулярных последовательностях и структурах обеспечивают альтернативу подходам , подходы к анализу последовательностей без выравнивания основанным на выравнивании.

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

Методы без выравнивания

Методы без выравнивания можно в общих чертах разделить на пять категорий: а) методы, основанные на частоте k -меров/слов, б) методы, основанные на длине общих подстрок, в) методы, основанные на количестве совпадений слов (с интервалами), d ) методы, основанные на микровыравниваниях , д) методы, основанные на теории информации и е) методы, основанные на графическом представлении. Подходы без выравнивания использовались при поиске сходства последовательностей. кластеризация и классификация последовательностей, и в последнее время в филогенетике ( Рисунок 1 ).

Считается, что такой молекулярно-филогенический анализ с использованием подходов без выравнивания является частью филогеномики следующего поколения . В ряде обзорных статей представлен углубленный обзор методов анализа последовательностей без выравнивания.

AFproject — это международное сотрудничество по тестированию и сравнению программных инструментов для сравнения последовательностей без выравнивания.

Методы, основанные на частоте k -меров/слов

Популярные методы, основанные на частоте k -меров/слов, включают профиль частоты признаков (FFP), Вектор состава (CV), Распределение времени возврата (RTD), представление игры частотного хаоса (FCGR). и слова с пробелами.

Профиль частоты функций (FFP)

Методология, используемая в методе, основанном на FFP, начинается с расчета количества каждого возможного k -мера (возможное количество k -меров для нуклеотидной последовательности: 4 ^к , а для последовательности белка: 20 ^к ) в последовательностях. Затем каждое количество k -меров в каждой последовательности нормализуется путем деления его на общее количество всех k -меров в этой последовательности. Это приводит к преобразованию каждой последовательности в ее характерный частотный профиль. Затем рассчитывается попарное расстояние между двумя последовательностями, расхождение Дженсена-Шеннона (JS) между их соответствующими FFP. Полученная таким образом матрица расстояний может быть использована для построения филогенетического дерева с использованием алгоритмов кластеризации, таких как объединение соседей , UPGMA и т. д.

Вектор состава (CV)

частота появления каждого возможного k В этом методе рассчитывается -мера в заданной последовательности. Следующим характерным шагом этого метода является вычитание случайного фона этих частот с использованием модели Маркова, чтобы уменьшить влияние случайных нейтральных мутаций и подчеркнуть роль избирательной эволюции. Нормализованным частотам присваивается фиксированный порядок для формирования вектора композиции (CV) данной последовательности. Затем функция косинусного расстояния используется для вычисления попарного расстояния между CV последовательностей. Полученная таким образом матрица расстояний может быть использована для построения филогенетического дерева с использованием алгоритмов кластеризации, таких как объединение соседей , UPGMA и т. д. Этот метод можно расширить, прибегнув к эффективным алгоритмам сопоставления с образцом, чтобы включить в вычисление векторов композиции: (i) все k -меры для любого значения k , (ii) все подстроки любой длины до произвольно установленного максимального значения k , (iii) все максимальные подстроки, где подстрока является максимальной, если ее расширение любым символом приведет к уменьшению ее появления считать.

Распределение времени возврата (RTD)

Метод, основанный на RTD, не вычисляет количество k -меров в последовательностях, а вычисляет время, необходимое для повторного появления к -мерс. Время относится к количеству остатков в последовательном появлении определенного k -мера. Таким образом, появление каждого k -мера в последовательности рассчитывается в форме RTD, который затем суммируется с использованием двух статистических параметров: среднего значения (μ) и стандартного отклонения (σ). Таким образом, каждая последовательность представляется в виде числового вектора размером 2⋅4. ^к содержащие µ и σ из 4 ^к РТД. Парное расстояние между последовательностями рассчитывается с использованием меры евклидового расстояния . Полученная таким образом матрица расстояний может быть использована для построения филогенетического дерева с использованием алгоритмов кластеризации, таких как объединение соседей , UPGMA и т. д. Недавний подход «Извлечение шаблонов посредством энтропийного поиска» (PEER) обеспечивает прямое определение длины k-мера и суммирует интервал встречаемости с использованием энтропии. .

Представление игры частотного хаоса (FCGR)

Методы FCGR произошли от метода представления игры хаоса (CGR), который обеспечивает независимое от масштаба представление геномных последовательностей. CGR можно разделить линиями сетки, где каждый квадрат сетки обозначает появление олигонуклеотидов определенной длины в последовательности. Такое представление CGR называется представлением игры частотного хаоса (FCGR). Это приводит к представлению каждой последовательности в FCGR. Парное расстояние между FCGR последовательностями можно рассчитать с использованием расстояния Пирсона, расстояния Хэмминга или евклидова расстояния.

Частоты пробельных слов

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

Методы, основанные на длине общих подстрок

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

Средняя общая подстрока (ACS)

В этом подходе для выбранной пары последовательностей (A и B длиной n и m соответственно) самая длинная подстрока в одной последовательности (A) идентифицируется , начинающаяся с некоторой позиции, которая точно совпадает с другой последовательностью (B) в любой позиции. Таким образом вычисляются длины самых длинных подстрок, начинающихся в разных позициях последовательности A и имеющих точные совпадения в некоторых позициях последовательности B. Все эти длины усредняются для получения меры $L(A,B)$. Интуитивно, чем больше $L(A,B)$, тем более похожи две последовательности. Чтобы учесть различия в длине последовательностей, $L(A,B)$ нормализован [т.е. $L(A,B)/\log(m)$]. Это дает меру сходства между последовательностями.

Чтобы получить меру расстояния, обратная мера сходства берется поправочный член , чтобы гарантировать, что и из нее вычитается $d(A,A)$ будет нулевым. Таким образом

$d(A,B)=\left[{\frac {\log m}{L(A,B)}}\right]-\left[{\frac {\log n}{L(A,A)}}\right].$

Эта мера $d(A,B)$ несимметрично, поэтому необходимо вычислить $d_{s}(A,B)=d_{s}(B,A)=(d(A,B)+d(B,A))/2$, что дает окончательную меру ACS между двумя строками (A и B). Поиск подпоследовательности/подстроки может быть эффективно выполнен с помощьюиспользование суффиксных деревьев .

k - подход к среднему несоответствию общей подстроки (kmacs)

Этот подход является обобщением подхода ACS. Чтобы определить расстояние между двумя последовательностями ДНК или белка, kmacs оценивает для каждой позиции i первой последовательности самую длинную подстроку, начинающуюся с i и соответствующую подстроке второй последовательности с числом несоответствий до k . Он определяет среднее значение этих значений как меру сходства между последовательностями и превращает его в меру симметричного расстояния. Kmacs не вычисляет точные подстроки с k- несоответствием, поскольку это было бы слишком затратно в вычислениях, но аппроксимирует такие подстроки.

Дистанция мутации (Кр)

Этот подход тесно связан с ACS, который рассчитывает количество замен на сайт между двумя последовательностями ДНК, используя кратчайший путь. отсутствующая подстрока (называемая шустрингом).

Распределение длин общих подстрок с k-несоответствием

Этот подход использует программу kmacs для расчета самых длинных общих подстрок с числом несоответствий до k для пары последовательностей ДНК. Затем филогенетическое расстояние между последовательностями можно оценить по локальному максимуму в распределении длин общих подстрок с k-несоответствием.

Методы, основанные на количестве совпадений слов (через интервалы)

$D_{2}^{S}$ и $D_{2}^{*}$

Эти подходы являются вариантами $D_{2}$ статистика, которая подсчитывает количество $k$-mer соответствует двум последовательностям. Они улучшают простые $D_{2}$ статистику с учетом фонового распределения сравниваемых последовательностей.

МАШ

Это чрезвычайно быстрый метод, который использует стратегию нижнего эскиза MinHash для оценки индекса Жаккара мультимножеств $k$-меры двух входных последовательностей. То есть оценивается соотношение $k$-mer соответствует общему количеству $k$-меры последовательностей. Это, в свою очередь, можно использовать для оценки эволюционных расстояний между сравниваемыми последовательностями, измеряемых как количество замен на позицию последовательности с тех пор, как последовательности произошли от их последнего общего предка.

Склон-Дерево

Этот подход рассчитывает значение расстояния между двумя белковыми последовательностями на основе убывания количества $k$-mer соответствует, если $k$ увеличивается.

Склон-СпаМ

Этот метод вычисляет число $N_{k}$ из $k$-mer или совпадения слов через пробел ( SpaM ) для разных значений длины слова или количества совпадающих позиций $k$ в базовом шаблоне соответственно. Наклон аффинно-линейной функции $F$ это зависит от $N_{k}$ рассчитывается для оценки расстояния Джукса-Кантора между входными последовательностями.

Сумерки

Скмер вычисляет расстояния между видами на основе несобранных считываний секвенирования. Подобно MASH , он использует индекс Жаккара для наборов $k$-меры из входных последовательностей. В отличие от MASH , программа по-прежнему точна при небольшом охвате секвенирования, поэтому ее можно использовать для скимминга генома .

Методы, основанные на микровыравниваниях

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

Ко-филог

Этот метод ищет так называемые структуры , которые определяются как пары совпадений k -меров между двумя последовательностями ДНК, которые находятся на расстоянии одной позиции в обеих последовательностях. Два совпадения k -мера называются контекстом , положение между ними называется объектом . Затем Co-phylog определяет расстояние между двумя последовательностями, долю таких структур , для которых два нуклеотида в объекте различны. Этот подход может быть применен к несобранным чтениям секвенирования.

Энди

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

Фильтрованные совпадения между словами через пробел (FSWM)

FSWM использует заранее определенный двоичный шаблон P, представляющий так называемые позиции совпадения и позиции безразличия . Затем для пары входных последовательностей ДНК он ищет пробельных слов относительно P , т.е. локальные выравнивания без пробелов с совпадающими нуклеотидами в позициях совпадения P совпадения и возможные несовпадения в позициях без пробелов . Ложные совпадения слов через пробел с низкой оценкой отбрасываются, эволюционные расстояния между входными последовательностями оцениваются на основе нуклеотидов, выровненных друг с другом в неважных положениях оставшихся гомологичных совпадений слов через пробел. FSWM адаптирован для оценки расстояний на основе несобранных чтений NGS, эта версия программы называется Read-SpaM .

Прот-СпаМ

Prot-SpaM ( ) на основе протеома совпадения пространственных слов М — это реализация алгоритма FSWM для частичных или целых последовательностей протеома.

Мульти-СпаМ

Multi-SpaM ( множественные с пробелами слов совпадения ) — это подход к реконструкции филогении на основе генома, который расширяет идею FSWM до сравнения множественных последовательностей. Учитывая бинарный шаблон P совпадающих позиций и ненужных позиций , программа ищет P -блоки, то есть локальные четырехсторонние выравнивания без пробелов с совпадающими нуклеотидами в совпадающих позициях P позициях . и возможными несовпадениями в несовпадающих - посты по уходу . Такие четырехсторонние выравнивания случайным образом выбираются из набора входных последовательностей генома. Для каждого P рассчитывается топология некорневого дерева -блока с помощью RAxML . Затем программа Quartet MaxCut используется для расчета супердерева из этих деревьев.

Методы, основанные на теории информации

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

Базово-базовая корреляция (BBC)

Корреляция оснований-оснований (BBC) преобразует последовательность генома в уникальный 16-мерный числовой вектор с помощью следующего уравнения:

$T_{ij}(K)=\sum _{\ell =1}^{K}P_{ij}(\ell )\cdot \log _{2}\left({\frac {P_{ij}(\ell )}{P_{i}P_{j}}}\right)$

The $P_{i}$ и $P_{j}$ обозначает вероятности оснований i и j в геноме. $P_{ij}(\ell )$ указывает вероятность наличия оснований i и j на расстоянии ℓ в геноме. Параметр K указывает максимальное расстояние между базами i и j . Вариация значений 16 параметров отражает изменение содержания и длины генома.

Информационная корреляция и частичная информационная корреляция (IC-PIC)

Метод, основанный на IC-PIC ( информационная корреляция и частичная информационная корреляция), использует свойство базовой корреляции последовательности ДНК. IC и PIC рассчитывались по следующим формулам:

$IC_{\ell }=-2\sum _{i}P_{i}\log _{2}P_{i}+\sum _{ij}P_{ij}(\ell )\log _{2}P_{ij}(\ell )$

$PIC_{ij}(\ell )=(P_{ij}(\ell )-P_{i}P_{j}(\ell ))^{2}$

Окончательный вектор получается следующим образом:

$V={IC_{\ell } \over PIC_{ij}(\ell )}{\text{ where }}\ell \in \left\{\ell _{0},\ell _{0}+1,\ldots ,\ell _{0}+n\right\},$

который определяет диапазон расстояний между базами.

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

Сжатие

Примерами являются эффективные аппроксимации сложности по Колмогорову , например сложность Лемпеля-Зива . Обычно методы, основанные на сжатии, используют взаимную информацию между последовательностями. Это выражается в условной колмогоровской сложности , то есть длине кратчайшей саморазграничивающейся программы, необходимой для генерации строки с учетом предварительного знания другой строки. Эта мера имеет отношение к измерению k -слов в последовательности, поскольку их можно легко использовать для генерации последовательности. Иногда это трудоемкий метод. Теоретической основой подхода колмогоровской сложности было предложили Беннетт, Гакс, Ли, Витаньи и Зурек (1998), предложив информационную дистанцию . Поскольку колмогоровская сложность невычислима, она была аппроксимирована алгоритмами сжатия. Чем лучше они сжимают, тем лучше. Ли, Бэджер, Чен, Квонг, Кирни и Чжан (2001) использовали неоптимальную, но нормализованную форму этого подхода: а оптимальная нормализованная форма, предложенная Ли, Ченом, Ли, Ма и Витаньи (2003), появилась в и более подробно и доказано Чилибраси и Витаньи (2005). Оту и Саюд (2003) использовали метод сложности Лемпеля-Зива для построения пяти различных мер расстояния для построения филогенетического дерева .

Сжатие контекстного моделирования

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

Методы, основанные на графическом представлении

Повторяющиеся карты

Использование итерированных карт для анализа последовательностей было впервые предложено Х. Дж. Джеффри в 1990 году. когда он предложил применить игру хаоса для отображения геномных последовательностей на единичный квадрат. В этом отчете эта процедура была названа «Представление игры хаоса» (CGR). Однако всего три года спустя этот подход был впервые отвергнут Н. Гольдманом как проекция марковской таблицы переходов. Это возражение было отвергнуто к концу того же десятилетия, когда было обнаружено обратное: CGR биективно отображает марковский переход во фрактальное представление без порядка (без степени). Осознание того, что итерированные карты обеспечивают биективную карту между символическим пространством и числовым пространством, привело к выявлению множества подходов к сравнению и характеристике последовательностей без выравнивания. Эти разработки были рассмотрены в конце 2013 года JS Almeida. Ряд веб-приложений, таких как https://github.com/usm/usm.github.com/wiki , доступны для демонстрации того, как кодировать и сравнивать произвольные символьные последовательности таким образом, чтобы в полной мере использовать преимущества современного дистрибутива MapReduce, разработанного для облачных вычислений.

Сравнение методов, основанных на выравнивании, и методов, не требующих выравнивания.

Методы на основе выравнивания	Методы без выравнивания
Эти методы предполагают, что гомологичные области смежны (с промежутками).	Не предполагает такой близости гомологичных участков
Вычисляет все возможные попарные сравнения последовательностей; следовательно, вычислительно дорого	На основе появления подпоследовательностей; состав; недорог в вычислительном отношении, может требовать больших затрат памяти
Устоявшийся подход в филогеномике	Сравнительно недавно, и применение в филогеномике ограничено; требует дальнейшего тестирования на надежность и масштабируемость
Требуются модели замещения/эволюции.	Менее зависит от моделей замещения/эволюции
Чувствителен к стохастическим изменениям последовательностей, рекомбинации, горизонтальному (или латеральному) генетическому переносу, гетерогенности скорости и последовательностям различной длины, особенно когда сходство находится в «сумеречной зоне».	Менее чувствителен к стохастическим изменениям последовательностей, рекомбинации, горизонтальному (или латеральному) генетическому переносу, гетерогенности скорости и последовательностям различной длины.
В передовой практике используются алгоритмы вывода со сложностью не менее O(n 2 ); менее эффективный по времени	Алгоритмы вывода обычно O(n 2 ) или меньше; более эффективный по времени
Эвристический характер; статистическую значимость того, как показатели выравнивания связаны с гомологией, трудно оценить	Точные решения; статистическую значимость расстояний последовательностей (и степени сходства) можно легко оценить.
Полагается на динамическое программирование (затратное в вычислительном отношении), чтобы найти выравнивание, имеющее оптимальную оценку.	обходит дорогостоящее вычислительное динамическое программирование путем индексации количества слов или позиций во фрактальном пространстве.

Применение методов без выравнивания

• Геномные перестройки
• Молекулярная филогенетика
• Метагеномика
• Анализ данных последовательностей нового поколения
• Эпигеномика
• Штрих-кодирование видов
• Популяционная генетика
• Горизонтальный перенос генов
• Серо/генотипирование вирусов
• Прогноз аллергенности
• Открытие SNP
• Обнаружение рекомбинации
• Классификация вирусов
• Таксономическая идентификация архей
• Идентификация регионов низкой сложности

Список веб-серверов/программного обеспечения для методов без выравнивания

Имя	Описание	Доступность	Ссылка
Проткомп	Подход к оценке наиболее выраженных функций	ПРОТКОМП
кмакс	подход k - несоответствие средней общей подстроки	кмакс
Слова через пробел	Частоты пробельных слов	слова через пробел
Ко-филог	метод микровыравнивания без сборки	Ко-филог
Прот-СпаМ	Соответствие пробельных слов на основе протеома	Прот-СпаМ
ФСВМ	Отфильтрованные совпадения слов через пробел	ФСВМ
ФФП	Филогения на основе профиля частоты признаков	ФФП
вариатор	Сервер на основе вектора состава для филогении	вариатор
Филогения РТД	Сервер на основе распределения времени возврата для филогении	Филогения РТД
АГП	Мультиметодный веб-сервер для филогении генома без выравнивания	АГП
Альфы	Обнаружение локального сходства вирусных и бактериальных геномов без выравнивания	Альфы
без кофеина+пи	Расчет расстояния с использованием методов без выравнивания в PYthon	без кофеина+пи
Подтип Денге	Генотипирование вирусов денге на основе RTD	Подтип Денге
Типы ВЗН	Генотипирование вирусов Западного Нила на основе RTD	Типы ВЗН
АллергенФП	Прогнозирование аллергенности по отпечаткам пальцев дескриптора	АллергенФП
ксНП v2	Обнаружение SNP без выравнивания	ксНП v2
d2Инструменты	Сравнение метатранскриптомных образцов на основе k -кортежей частот	d2Инструменты
торопиться	Обнаружение рекомбинации с использованием SHustrings	торопиться
разгромить	Обнаружение и визуализация геномных перестроек	разгромить
Разбить++	Поиск и визуализация геномных перестроек	Разбить++
GScompare	Быстрая кластеризация бактериальных геномов на основе олигонуклеотидов	GScompare	–
КОМЕТА	Подтипирование вирусных последовательностей ВИЧ-1, ВИЧ-2 и ВГС без выравнивания	КОМЕТА
УСМ	Фрактальная картаУменьшите разложение выравнивания последовательностей	usm.github.io
СОКОЛ	Метод без выравнивания для определения метагеномного состава древней ДНК	СОКОЛ
Кракен	Таксономическая классификация с использованием точных совпадений k-меров	Кракен 2
ЦЛК	Филогенетические деревья с использованием сопоставления на основе k-меров без ссылок	Модуль CLC микробного генома
ОРЕЛ	Сверхбыстрый инструмент для поиска относительно отсутствующих слов в геномных данных.	ОРЕЛ2
АлкоР	Чрезвычайно эффективный метод идентификации и визуализации областей низкой сложности в геномных и протеомных последовательностях.	АлкоР

См. также

• Анализ последовательности
• Множественное выравнивание последовательностей
• Филогеномика
• Биоинформатика
• Метагеномика
• Секвенирование нового поколения
• Популяционная генетика
• SNP
• Программа обнаружения рекомбинации
• Снятие генома