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

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

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

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

Методы без выравнивания можно в целом разделить на пять категорий: a) методы, основанные на частоте k -мера/слова, b) методы, основанные на длине общих подстрок, c) методы, основанные на количестве (разнесенных) совпадений слов, d) методы, основанные на микровыравниваниях , e) методы, основанные на теории информации и f) методы, основанные на графическом представлении. Подходы без выравнивания использовались в поиске сходства последовательностей, ^[6] кластеризации и классификации последовательностей, ^[7] и совсем недавно в филогенетике ^[8]^[9] ( Рисунок 1 ).

Такие молекулярные филогенные анализы, использующие подходы без выравнивания, считаются частью филогеномики следующего поколения . ^[9] В ряде обзорных статей представлен углубленный обзор методов без выравнивания в анализе последовательностей. ^[1]^[10]^[11]^[12]^[13]^[14]^[15]

Проект AFproject представляет собой международное сотрудничество по оценке и сравнению программных инструментов для сравнения последовательностей без выравнивания. ^[16]

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

Популярные методы, основанные на частотах k -меров/слов, включают профиль частоты признаков (FFP), ^[17]^[18] вектор композиции (CV), ^[19]^[20] распределение времени возврата (RTD), ^[21] представление игры с частотным хаосом (FCGR). ^[22] и разнесенные слова. ^[23]

Профиль частоты признаков (FFP)

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

Вектор композиции (CV)

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

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

Метод на основе RTD не вычисляет количество k -меров в последовательностях, вместо этого он вычисляет время, необходимое для повторного появления k- меров. Время относится к количеству остатков в последовательном появлении конкретного k -мера. Таким образом, появление каждого k -мера в последовательности вычисляется в форме RTD, который затем суммируется с использованием двух статистических параметров: среднего (μ) и стандартного отклонения (σ). Таким образом, каждая последовательность представлена в форме числового вектора размером 2⋅4 ^k, содержащего μ и σ 4 ^k RTD. Попарное расстояние между последовательностями вычисляется с использованием евклидовой меры расстояния. Полученная таким образом матрица расстояний может быть использована для построения филогенетического дерева с использованием алгоритмов кластеризации, таких как присоединение соседей , UPGMA и т. д. Недавний подход Pattern Extraction through Entropy Retrieval (PEER) обеспечивает прямое обнаружение длины k-мера и суммирует интервал появления с использованием энтропии.

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

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

Частоты употребления слов с пробелами

В то время как большинство алгоритмов без выравнивания сравнивают состав слов последовательностей, Spaced Words использует шаблон позиций care и don't care. Появление слова с интервалом в последовательности затем определяется только символами в позициях совпадения, в то время как символы в позициях don't care игнорируются. Вместо сравнения частот смежных слов во входных последовательностях этот подход сравнивает частоты слов с интервалом в соответствии с предопределенным шаблоном. ^[23] Обратите внимание, что предопределенный шаблон может быть выбран путем анализа дисперсии числа совпадений, ^[28] вероятности первого появления в нескольких моделях, ^[29] или коэффициента корреляции Пирсона между ожидаемой частотой слова и истинным расстоянием выравнивания. ^[30]

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

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

Средняя общая подстрока (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].

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

к- подход с использованием средней общей подстроки несоответствия (kmacs)

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

Мутационные расстояния (Kr)

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

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

Этот подход использует программу kmacs ^[36] для вычисления самых длинных общих подстрок с несовпадением до k для пары последовательностей ДНК. Филогенетическое расстояние между последовательностями затем может быть оценено из локального максимума в распределении длины общих подстрок с несовпадением k. ^[38]

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

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

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

МАШ

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

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

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

Slope-SpaM

Этот метод вычисляет количество совпадений -mer или spaced-word ( SpaM ) для различных значений длины слова или количества позиций совпадений в базовом шаблоне соответственно. Наклон аффинно-линейной функции , которая зависит от , вычисляется для оценки расстояния Jukes-Cantor между входными последовательностями . ^[42] $N_{k}$ $к$ $к$ $F$ $N_{k}$

Скмер

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

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

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

Ко-филог

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

энди

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

Фильтрация совпадений с пробелами (FSWM)

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

Прот-СпаМ

Prot-SpaM ( Proteome -based Spaced -word Matches ) — это реализация алгоритма FSWM для частичных или полных последовательностей протеома. ^[48]

Мульти-СпаМ

Multi-SpaM ( Multiple Spa ced -word Matches ) — это подход к реконструкции филогении на основе генома, который расширяет идею FSWM до сравнения множественных последовательностей. ^[49] При наличии бинарного шаблона P позиций совпадений и позиций «неважно» программа ищет P -блоки, т. е. локальные четырехсторонние выравнивания без пробелов с совпадающими нуклеотидами в позициях совпадений P и возможными несовпадениями в позициях «неважно» . Такие четырехсторонние выравнивания случайным образом выбираются из набора входных последовательностей генома. Для каждого P -блока с помощью RAxML вычисляется топология некорневого дерева . ^[50] Затем программа Quartet MaxCut используется для вычисления супердерева из этих деревьев.

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

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

Базовая корреляция (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)

И обозначает вероятности оснований i и j в геноме. Указывает вероятность оснований i и j на расстоянии ℓ в геноме. Параметр K указывает максимальное расстояние между основаниями i и j . Изменение значений 16 параметров отражает изменение содержания и длины генома. ^[52]^[53]^[54] $P_{i}$ $P_{j}$ $P_{ij}(\ell )$

Корреляция информации и частичная корреляция информации (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{ где }}\ell \in \left\{\ell _{0},\ell _{0}+1,\ldots ,\ell _{0}+n\right\},

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

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

Сжатие

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

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

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

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

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

Использование итерационных карт для анализа последовательностей было впервые введено HJ Jefferey в 1990 году ^[26] , когда он предложил применить Chaos Game для отображения геномных последовательностей в единичный квадрат. В этом отчете процедура была названа Chaos Game Representation (CGR). Однако всего 3 года спустя этот подход был впервые отклонен как проекция таблицы марковских переходов N Goldman. ^[62] Это возражение было отклонено к концу того десятилетия, когда было обнаружено обратное — что CGR биективно отображает марковский переход во фрактальное, не имеющее порядка (степени) представление. ^[63] Осознание того, что итерационные карты обеспечивают биективное отображение между символическим пространством и числовым пространством, привело к выявлению множества подходов без выравнивания для сравнения и характеристики последовательностей. Эти разработки были рассмотрены в конце 2013 года Дж. С. Алмейдой в ^[64] . Ряд веб-приложений, таких как https://github.com/usm/usm.github.com/wiki, ^[65] доступны для демонстрации того, как кодировать и сравнивать произвольные символьные последовательности таким образом, чтобы в полной мере использовать преимущества современного дистрибутива MapReduce, разработанного для облачных вычислений.

Сравнение методов, основанных на выравнивании и не основанных на выравнивании

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

Геномные перестройки ^[67]^[68]
Молекулярная филогенетика ^[9]^[14]^[69]
Метагеномика ^[70]^[71]^[72]^[73]^[74]
Анализ данных последовательностей следующего поколения ^[70]^[30]
Эпигеномика ^[75]
Штрихкодирование видов ^[76]
Популяционная генетика ^[11]
Горизонтальный перенос генов ^[8]
Серо/генотипирование вирусов ^[21]^[77]^[78]
Прогнозирование аллергенности ^[79]
Открытие SNP ^[80]
Обнаружение рекомбинации ^[81]
Классификация вирусов ^[82]
Таксономическая идентификация архей ^[83]
Идентификация областей низкой сложности ^[84]

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

Смотрите также

Ссылки

^ ab Vinga S, Almeida J (март 2003 г.). «Сравнение последовательностей без выравнивания — обзор». Биоинформатика . 19 (4): 513–523. doi : 10.1093/bioinformatics/btg005 . PMID 12611807.
^ Ротберг Дж., Мерриман Б., Хиггс Г. (сентябрь 2012 г.). «Биоинформатика. Введение». Йельский журнал биологии и медицины . 85 (3): 305–308. PMC 3447194. PMID 23189382 .
^ Batzoglou S (март 2005 г.). «Многогранность выравнивания последовательностей». Briefings in Bioinformatics . 6 (1): 6–22. doi : 10.1093/bib/6.1.6 . PMID 15826353.
^ Маллан Л. (март 2006 г.). «Парное выравнивание последовательностей — это все о нас!». Briefings in Bioinformatics . 7 (1): 113–115. doi :10.1093/bib/bbk008. PMID 16761368.
^ Кемена С, Нотредам С (октябрь 2009 г.). «Предстоящие проблемы для методов выравнивания множественных последовательностей в эпоху высокой пропускной способности». Биоинформатика . 25 (19): 2455–2465. doi :10.1093/bioinformatics/btp452. PMC 2752613. PMID 19648142 .
^ Hide W, Burke J, Davison DB (1994). «Биологическая оценка d2, алгоритма для высокопроизводительного сравнения последовательностей». Журнал вычислительной биологии . 1 (3): 199–215. doi :10.1089/cmb.1994.1.199. PMID 8790465.
^ Miller RT, Christoffels AG, Gopalakrishnan C, Burke J, Ptitsyn AA, Broveak TR, Hide WA (ноябрь 1999 г.). «Комплексный подход к кластеризации экспрессированной последовательности генов человека: выравнивание тегов последовательности и консенсусная база знаний». Genome Research . 9 (11): 1143–1155. doi :10.1101/gr.9.11.1143. PMC 310831 . PMID 10568754.
^ abc Domazet-Lošo M, Haubold B (июнь 2011 г.). «Обнаружение локального сходства вирусных и бактериальных геномов без выравнивания». Биоинформатика . 27 (11): 1466–1472. doi : 10.1093/bioinformatics/btr176 . PMID 21471011.
^ abc Chan CX, Ragan MA (январь 2013 г.). «Филогеномика следующего поколения». Biology Direct . 8 : 3. doi : 10.1186/1745-6150-8-3 . PMC 3564786. PMID 23339707 .
^ Song K, Ren J, Reinert G , Deng M, Waterman MS, Sun F (май 2014 г.). «Новые разработки в области сравнения последовательностей без выравнивания: меры, статистика и секвенирование следующего поколения». Briefings in Bioinformatics . 15 (3): 343–353. doi :10.1093/bib/bbt067. PMC 4017329. PMID 24064230 .
^ ab Haubold B (май 2014). «Филогенетика без выравнивания и популяционная генетика». Briefings in Bioinformatics . 15 (3): 407–418. doi : 10.1093/bib/bbt083 . PMID 24291823.
^ Bonham-Carter O, Steele J, Bastola D (ноябрь 2014 г.). «Сравнение генетических последовательностей без выравнивания: обзор последних подходов по анализу слов». Briefings in Bioinformatics . 15 (6): 890–905. doi :10.1093/bib/bbt052. PMC 4296134. PMID 23904502 .
^ Zielezinski A, Vinga S, Almeida J, Karlowski WM (октябрь 2017 г.). «Сравнение последовательностей без выравнивания: преимущества, применение и инструменты». Genome Biology . 18 (1): 186. doi : 10.1186/s13059-017-1319-7 . PMC 5627421 . PMID 28974235.
^ ab Bernard G, Chan CX, Chan YB, Chua XY, Cong Y, Hogan JM и др. (март 2019 г.). «Вывод иерархических и ретикулярных филогеномных отношений без выравнивания». Briefings in Bioinformatics . 20 (2): 426–435. doi :10.1093/bib/bbx067. PMC 6433738. PMID 28673025 .
^ Ren J, Bai X, Lu YY, Tang K, Wang Y, Reinert G, Sun F (июль 2018 г.). «Анализ последовательностей без выравнивания и его применение». Annual Review of Biomedical Data Science . 1 : 93–114. arXiv : 1803.09727 . Bibcode : 2018arXiv180309727R. doi : 10.1146/annurev-biodatasci-080917-013431. PMC 6905628. PMID 31828235 .
^ Zielezinski A, Girgis HZ, Bernard G, Leimeister CA, Tang K, Dencker T и др. (Июль 2019 г.). «Бенчмаркинг методов сравнения последовательностей без выравнивания». Genome Biology . 20 (1): 144. doi : 10.1186/s13059-019-1755-7 . PMC 6659240 . PMID 31345254.
^ ab Sims GE, Jun SR, Wu GA, Kim SH (октябрь 2009 г.). «Полногеномная филогения млекопитающих: эволюционная информация в генных и негенных регионах». Труды Национальной академии наук Соединенных Штатов Америки . 106 (40): 17077–17082. Bibcode : 2009PNAS..10617077S. doi : 10.1073/pnas.0909377106 . PMC 2761373. PMID 19805074 .
^ Sims GE, Kim SH (май 2011). "Полногеномная филогения группы Escherichia coli/Shigella по профилям частот признаков (FFP)". Труды Национальной академии наук Соединенных Штатов Америки . 108 (20): 8329–8334. Bibcode : 2011PNAS..108.8329S. doi : 10.1073/pnas.1105168108 . PMC 3100984. PMID 21536867 .
^ Gao L, Qi J (март 2007 г.). "Полногеномная молекулярная филогения крупных вирусов dsDNA с использованием метода композиционного вектора". BMC Evolutionary Biology . 7 (1): 41. Bibcode :2007BMCEE...7...41G. doi : 10.1186/1471-2148-7-41 . PMC 1839080 . PMID 17359548.
^ Wang H, Xu Z, Gao L, Hao B (август 2009). "Филогения грибов на основе 82 полных геномов с использованием метода композиционного вектора". BMC Evolutionary Biology . 9 (1): 195. Bibcode :2009BMCEE...9..195W. doi : 10.1186/1471-2148-9-195 . PMC 3087519 . PMID 19664262.
^ abcd Колекар П., Кейл М., Кулкарни-Кейл У. (ноябрь 2012 г.). «Мера расстояния без выравнивания на основе распределения времени возврата для анализа последовательностей: приложения к кластеризации, молекулярной филогении и подтипированию». Молекулярная филогенетика и эволюция . 65 (2): 510–522. doi :10.1016/j.ympev.2012.07.003. PMID 22820020.
^ Hatje K, Kollmar M (2012). "Филогенетический анализ клады brassicales на основе метода сравнения последовательностей без выравнивания". Frontiers in Plant Science . 3 : 192. doi : 10.3389/fpls.2012.00192 . PMC 3429886 . PMID 22952468.
^ abc Leimeister CA, Boden M, Horwege S, Lindner S, Morgenstern B (июль 2014 г.). «Быстрое сравнение последовательностей без выравнивания с использованием частот пробельных слов». Биоинформатика . 30 (14): 1991–1999. doi :10.1093/bioinformatics/btu177. PMC 4080745. PMID 24700317 .
^ Апостолико А, Денас О (октябрь 2008 г.). "Быстрые алгоритмы для вычисления расстояний последовательностей путем исчерпывающего составления подстрок". Алгоритмы для молекулярной биологии . 3 : 13. doi : 10.1186/1748-7188-3-13 . PMC 2615014. PMID 18957094 .
^ Апостолико А, Денас О, Дресс А (сентябрь 2010 г.). «Эффективные инструменты для сравнительного анализа подстрок». Журнал биотехнологии . 149 (3): 120–126. doi :10.1016/j.jbiotec.2010.05.006. PMID 20682467.
^ ab Jeffrey HJ (апрель 1990 г.). «Представление структуры гена в виде игры хаоса». Nucleic Acids Research . 18 (8): 2163–2170. doi :10.1093/nar/18.8.2163. PMC 330698. PMID 2336393 .
^ Wang Y, Hill K, Singh S, Kari L (февраль 2005 г.). «Спектр геномных сигнатур: от динуклеотидов до представления игры хаоса». Gene . 346 : 173–185. doi :10.1016/j.gene.2004.10.021. PMID 15716010.
^ Hahn L, Leimeister CA, Ounit R, Lonardi S, Morgenstern B (октябрь 2016 г.). "rasbhari: Оптимизация разнесенных семян для поиска в базе данных, картирования чтения и сравнения последовательностей без выравнивания". PLOS Computational Biology . 12 (10): e1005107. arXiv : 1511.04001 . Bibcode : 2016PLSCB..12E5107H. doi : 10.1371/journal.pcbi.1005107 . PMC 5070788. PMID 27760124 .
^ Noé L (14 февраля 2017 г.). "Лучшие хиты 11110110111: выбор без модели и расчет чувствительности без параметров для разнесенных семян". Алгоритмы для молекулярной биологии . 12 (1): 1. doi : 10.1186/s13015-017-0092-1 . PMC 5310094. PMID 28289437 .
^ ab Noé L, Martin DE (декабрь 2014 г.). «Критерий покрытия для разнесенных семян и его применение для поддержки строковых ядер векторной машины и расстояний k-меров». Журнал вычислительной биологии . 21 (12): 947–963. arXiv : 1412.2587 . Bibcode : 2014arXiv1412.2587N. doi : 10.1089/cmb.2014.0173. PMC 4253314. PMID 25393923 .
^ Gusfield D (1997). Алгоритмы на строках, деревьях и последовательностях: компьютерная наука и вычислительная биология (Переиздано (с исправленным) ред.). Кембридж [ua]: Cambridge Univ. Press. ISBN 9780521585194.
^ Ulitsky I, Burstein D, Tuller T, Chor B (март 2006). «Подход к филогеномной реконструкции на основе средней общей подстроки». Журнал вычислительной биологии . 13 (2): 336–350. CiteSeerX 10.1.1.106.5122 . doi :10.1089/cmb.2006.13.336. PMID 16597244.
^ Weiner P (1973). «Линейные алгоритмы сопоставления шаблонов». 14-й ежегодный симпозиум по теории коммутации и автоматов (SWAT 1973) . стр. 1–11. CiteSeerX 10.1.1.474.9582 . doi :10.1109/SWAT.1973.13.
^ He D (2006). «Использование суффиксного дерева для обнаружения сложных повторяющихся паттернов в последовательностях ДНК». Международная конференция IEEE Engineering in Medicine and Biology Society 2006 года . Том 1. С. 3474–7. doi :10.1109/IEMBS.2006.260445. ISBN 978-1-4244-0032-4. PMID 17945779. S2CID 5953866.
^ Välimäki N, Gerlach W, Dixit K, Mäkinen V (март 2007). «Сжатое суффиксное дерево — основа для анализа последовательностей в масштабе генома». Биоинформатика . 23 (5): 629–630. doi : 10.1093/bioinformatics/btl681 . PMID 17237063.
^ abc Leimeister CA, Morgenstern B (июль 2014 г.). "Kmacs: подход k-mismatch average common substring к сравнению последовательностей без выравнивания". Биоинформатика . 30 (14): 2000–2008. doi :10.1093/bioinformatics/btu331. PMC 4080746. PMID 24828656 .
^ Haubold B, Pfaffelhuber P, Domazet-Loso M, Wiehe T (октябрь 2009 г.). «Оценка расстояний мутаций из невыровненных геномов». Журнал вычислительной биологии . 16 (10): 1487–1500. doi :10.1089/cmb.2009.0106. hdl : 11858/00-001M-0000-000F-D624-D . PMID 19803738.
^ Morgenstern B, Schöbel S, Leimeister CA (2017). "Реконструкция филогении на основе распределения длины общих подстрок k-несовпадений". Алгоритмы для молекулярной биологии . 12 : 27. doi : 10.1186/s13015-017-0118-8 . PMC 5724348. PMID 29238399 .
^ Reinert G, Chew D, Sun F, Waterman MS (декабрь 2009 г.). «Сравнение последовательностей без выравнивания (I): статистика и мощность». Journal of Computational Biology . 16 (12): 1615–1634. doi :10.1089/cmb.2009.0198. PMC 2818754 . PMID 20001252.
^ Ондов BD, Треанген TJ, Мелстед P, Маллони AB, Бергман NH, Корен S, Филлиппи AM (июнь 2016 г.). "Mash: быстрая оценка расстояний генома и метагенома с использованием MinHash". Genome Biology . 17 (1): 132. doi : 10.1186/s13059-016-0997-x . PMC 4915045. PMID 27323842 .
^ Бромберг Р., Гришин Н.В., Отвиновски З. (июнь 2016 г.). «Реконструкция филогении с помощью метода без выравнивания, который корректирует горизонтальный перенос генов». PLOS Computational Biology . 12 (6): e1004985. Bibcode : 2016PLSCB..12E4985B. doi : 10.1371/journal.pcbi.1004985 . PMC 4918981. PMID 27336403 .
^ Röhling S, Linne A, Schellhorn J, Hosseini M, Dencker T, Morgenstern B (2020). «Число совпадений k-меров между двумя последовательностями ДНК как функция k и приложения для оценки филогенетических расстояний». PLOS ONE . 15 (2): e0228070. Bibcode : 2020PLoSO..1528070R. doi : 10.1371/journal.pone.0228070 . PMC 7010260. PMID 32040534 .
^ Sarmashghi S, Bohmann K, P Gilbert MT, Bafna V, Mirarab S (февраль 2019 г.). "Skmer: идентификация образцов без сборки и выравнивания с использованием геномных скимов". Genome Biology . 20 (1): 34. doi : 10.1186/s13059-019-1632-4 . PMC 6374904 . PMID 30760303.
^ ab Yi H, Jin L (апрель 2013 г.). «Co-phylog: an assembly-free phylogenomic approach for close related organizations». Nucleic Acids Research . 41 (7): e75. doi :10.1093/nar/gkt003. PMC 3627563. PMID 23335788 .
^ Хаубольд Б., Клётцль Ф., Пфаффельхубер П. (апрель 2015 г.). «andi: быстрая и точная оценка эволюционных расстояний между близкородственными геномами». Биоинформатика . 31 (8): 1169–1175. doi : 10.1093/bioinformatics/btu815 . PMID 25504847.
^ ab Leimeister CA, Sohrabi-Jahromi S, Morgenstern B (апрель 2017 г.). «Быстрая и точная реконструкция филогении с использованием отфильтрованных совпадений между словами». Bioinformatics . 33 (7): 971–979. doi :10.1093/bioinformatics/btw776. PMC 5409309 . PMID 28073754.
^ Lau AK, Dörrer S, Leimeister CA, Bleidorn C, Morgenstern B (декабрь 2019 г.). «Read-SpaM: сравнение бактериальных геномов без сборки и выравнивания с низким покрытием секвенирования». BMC Bioinformatics . 20 (Suppl 20): 638. doi : 10.1186/s12859-019-3205-7 . PMC 6916211 . PMID 31842735.
^ ab Leimeister CA, Schellhorn J, Dörrer S, Gerth M, Bleidorn C, Morgenstern B (март 2019 г.). "Prot-SpaM: быстрая реконструкция филогении без выравнивания на основе последовательностей всего протеома". GigaScience . 8 (3): giy148. doi :10.1093/gigascience/giy148. PMC 6436989 . PMID 30535314.
^ Dencker T, Leimeister CA, Gerth M, Bleidorn C, Snir S, Morgenstern B (март 2020 г.). «Multi-SpaM: подход максимального правдоподобия к реконструкции филогении с использованием множественных совпадений с пробелами и деревьев квартетов». NAR Genomics and Bioinformatics . 2 (1): lqz013. doi : 10.1093/nargab/lqz013 . PMC 7671388 . PMID 33575565.
^ Stamatakis A (ноябрь 2006 г.). «RAxML-VI-HPC: филогенетический анализ на основе максимального правдоподобия с тысячами таксонов и смешанными моделями». Биоинформатика . 22 (21): 2688–2690. doi : 10.1093/bioinformatics/btl446 . PMID 16928733.
^ Vinga S (май 2014). «Применение теории информации для анализа биологических последовательностей». Briefings in Bioinformatics . 15 (3): 376–389. doi : 10.1093/bib/bbt068 . PMC 7109941. PMID 24058049 .
^ Liu Z, Meng J, Sun X (апрель 2008 г.). «Новый основанный на признаках метод филогенетического анализа всего генома без выравнивания: применение к генотипированию и подтипированию HEV». Biochemical and Biophysical Research Communications . 368 (2): 223–230. doi :10.1016/j.bbrc.2008.01.070. PMID 18230342.
^ Лю Ж., Сан Х. (2008). «Филогения коронавируса на основе корреляции основания». Международный журнал исследований и приложений биоинформатики . 4 (2): 211–220. doi : 10.1504/ijbra.2008.018347. PMID 18490264.
^ Cheng J, Zeng X, Ren G, Liu Z (март 2013 г.). "CGAP: новая комплексная платформа для сравнительного анализа геномов хлоропластов". BMC Bioinformatics . 14 : 95. doi : 10.1186/1471-2105-14-95 . PMC 3636126. PMID 23496817 .
^ Gao Y, Luo L (январь 2012 г.). «Геномная филогения вирусов dsDNA с использованием нового метода без выравнивания». Gene . 492 (1): 309–314. doi :10.1016/j.gene.2011.11.004. PMID 22100880.
^ Беннетт, CH, Гач, П., Ли, М., Витаний, П. и Журек, В., Информационное расстояние, IEEE Trans. Inform. Theory, 44, 1407--1423
^ Ли, М., Баджер, Дж. Х., Чен, Х., Квонг, С., Кирни, П. и Чжан, Х., (2001) Расстояние последовательностей на основе информации и его применение к филогении всего митохондриального генома. Биоинформатика, 17:(2001), 149--154
^ M. Li, X. Chen, X. Li, B. Ma, PMB Vitanyi. Метрика сходства, IEEE Trans. Inform. Th., 50:12(2004), 3250--3264
^ RL Cilibrasi и PMB Vitaany, Кластеризация путем сжатия, IEEE Trans. Информат. Тс., 51:4(2005), 1523--1545
^ Otu HH, Sayood K (ноябрь 2003 г.). «Новая мера расстояния последовательности для построения филогенетического дерева». Биоинформатика . 19 (16): 2122–2130. doi : 10.1093/bioinformatics/btg295 . PMID 14594718.
↑ Пиньо А.Дж., Гарсия С.П., Пратас Д., Феррейра П.Дж. (21 ноября 2013 г.). «Краткий обзор последовательностей ДНК». ПЛОС ОДИН . 8 (11): е79922. Бибкод : 2013PLoSO...879922P. дои : 10.1371/journal.pone.0079922 . ПМЦ 3836782 . ПМИД 24278218.
^ Goldman N (май 1993). «Частоты нуклеотидов, динуклеотидов и тринуклеотидов объясняют закономерности, наблюдаемые в представлениях последовательностей ДНК в виде игр хаоса». Nucleic Acids Research . 21 (10): 2487–2491. doi :10.1093/nar/21.10.2487. PMC 309551. PMID 8506142 .
^ Almeida JS, Carriço JA, Maretzek A, Noble PA, Fletcher M (май 2001 г.). «Анализ геномных последовательностей с помощью представления игр хаоса». Биоинформатика . 17 (5): 429–437. doi : 10.1093/bioinformatics/17.5.429 . PMID 11331237.
^ Almeida JS (май 2014 г.). «Анализ последовательностей с помощью итерационных карт, обзор». Briefings in Bioinformatics . 15 (3): 369–375. doi :10.1093/bib/bbt072. PMC 4017330. PMID 24162172.
^ ab Almeida JS, Grüneberg A, Maass W, Vinga S (май 2012 г.). "Fractal MapReduce разложение выравнивания последовательностей". Алгоритмы для молекулярной биологии . 7 (1): 12. doi : 10.1186/1748-7188-7-12 . PMC 3394223. PMID 22551205 .
^ Vinga S, Carvalho AM, Francisco AP, Russo LM, Almeida JS (май 2012 г.). «Соответствие образцу посредством представления игры хаоса: объединение числовых и дискретных структур данных для анализа биологических последовательностей». Алгоритмы для молекулярной биологии . 7 (1): 10. doi : 10.1186/1748-7188-7-10 . PMC 3402988. PMID 22551152.
^ ab Pratas D, Silva RM, Pinho AJ, Ferreira PJ (май 2015 г.). "Метод поиска и визуализации перестроек между парами последовательностей ДНК без выравнивания". Scientific Reports . 5 (10203): 10203. Bibcode :2015NatSR...510203P. doi :10.1038/srep10203. PMC 4434998 . PMID 25984837.
^ ab Hosseini M, Pratas D, Morgenstern B, Pinho AJ (май 2020 г.). «Smash++: инструмент без выравнивания и с эффективным использованием памяти для поиска геномных перестроек». GigaScience . 9 (5): giaa048. doi : 10.1093/gigascience/giaa048 . PMC 7238676 . PMID 32432328.
^ Бернард Г., Гринфилд П., Раган МА., Чан С.Х. (20 ноября 2018 г.). «Сходство k-меров, сети микробных геномов и таксономический ранг». mSystems . 3 (6): e00257–18. doi :10.1128/mSystems.00257-18. PMC 6247013 . PMID 30505941.
^ ab Song K, Ren J, Reinert G, Deng M, Waterman MS, Sun F (май 2014 г.). «Новые разработки в области сравнения последовательностей без выравнивания: меры, статистика и секвенирование следующего поколения». Briefings in Bioinformatics . 15 (3): 343–353. doi :10.1093/bib/bbt067. PMC 4017329. PMID 24064230 .
^ Břinda K, Sykulski M, Kucherov G (ноябрь 2015 г.). «Разнесенные семена улучшают метагеномную классификацию на основе k-меров». Биоинформатика . 31 (22): 3584–3592. arXiv : 1502.06256 . Bibcode : 2015arXiv150206256B. doi : 10.1093/bioinformatics/btv419. PMID 26209798. S2CID 8626694.
^ Ounit R, Lonardi S (декабрь 2016 г.). «Более высокая чувствительность классификации коротких метагеномных прочтений с CLARK-S». Биоинформатика . 32 (24): 3823–3825. doi : 10.1093/bioinformatics/btw542 . PMID 27540266.
^ аб Пратас Д., Пиньо А.Дж., Силва Р.М., Родригес Х.М., Хоссейни М., Каэтано Т., Феррейра П.Дж. (февраль 2018 г.). «СОКОЛ: метод определения метагеномного состава древней ДНК». bioRxiv 10.1101/267179 .
^ ab Wood DE, Salzberg SL (март 2014 г.). «Kraken: сверхбыстрая классификация метагеномных последовательностей с использованием точных выравниваний». Genome Biology . 15 (3): R46. doi : 10.1186/gb-2014-15-3-r46 . PMC 4053813 . PMID 24580807.
^ Pinello L, Lo Bosco G, Yuan GC (май 2014). «Применение методов без выравнивания в эпигеномике». Briefings in Bioinformatics . 15 (3): 419–430. doi :10.1093/bib/bbt078. PMC 4017331. PMID 24197932 .
^ La Rosa M, Fiannaca A, Rizzo R, Urso A (2013). «Анализ последовательностей штрихкодов без выравнивания с помощью методов на основе сжатия». BMC Bioinformatics . 14 (Suppl 7): S4. doi : 10.1186/1471-2105-14-S7-S4 . PMC 3633054. PMID 23815444 .
^ ab Kolekar P, Hake N, Kale M, Kulkarni-Kale U (март 2014 г.). "WNV Typer: сервер для генотипирования вирусов Западного Нила с использованием метода без выравнивания, основанного на распределении времени возврата". Journal of Virological Methods . 198 : 41–55. doi : 10.1016/j.jviromet.2013.12.012 . PMID 24388930.
^ ab Struck D, Lawyer G, Ternes AM, Schmit JC, Bercoff DP (октябрь 2014 г.). "COMET: адаптивное контекстно-ориентированное моделирование для сверхбыстрой идентификации подтипа ВИЧ-1". Nucleic Acids Research . 42 (18): e144. doi :10.1093/nar/gku739. PMC 4191385. PMID 25120265 .
^ ab Димитров И, Нанева Л, Дойчинова И, Бангов И (март 2014 г.). «AllergenFP: прогнозирование аллергенности по отпечаткам дескрипторов». Биоинформатика . 30 (6): 846–851. doi : 10.1093/bioinformatics/btt619 . PMID 24167156.
^ ab Gardner SN, Hall BG (9 декабря 2013 г.). «Когда выравнивания всего генома просто не работают: программное обеспечение kSNP v2 для обнаружения однонуклеотидных полиморфизмов без выравнивания и филогенетики сотен микробных геномов». PLOS ONE . 8 (12): e81760. Bibcode :2013PLoSO...881760G. doi : 10.1371/journal.pone.0081760 . PMC 3857212 . PMID 24349125.
^ ab Haubold B, Krause L, Horn T, Pfaffelhuber P (декабрь 2013 г.). «Тест на рекомбинацию без выравнивания». Биоинформатика . 29 (24): 3121–3127. doi :10.1093/bioinformatics/btt550. PMC 5994939. PMID 24064419 .
^ Сильва Дж. М., Пратас Д., Каэтано Т., Матос С. (август 2022 г.). «Сложность вирусных геномов». ГигаСайенс . 11 : 1–16. doi : 10.1093/gigascience/giac079. ПМЦ 9366995 . ПМИД 35950839.
^ Silva JM, Pratas D, Caetano T, Matos S (2022), Pinho AJ, Georgieva P, Teixeira LF, Sánchez JA (ред.), «Классификация последовательностей архей на основе признаков с использованием методов, основанных на сжатии», Распознавание образов и анализ изображений , Конспект лекций по информатике, т. 13256, Cham: Springer International Publishing, стр. 309–320, doi : 10.1007/978-3-031-04881-4_25, ISBN 978-3-031-04880-7, получено 2022-08-31
^ аб Силва Дж. М., Ци В, Пиньо А. Дж., Пратас Д. (декабрь 2022 г.). «AlcoR: моделирование, картирование и визуализация областей низкой сложности в биологических данных без выравнивания». ГигаСайенс . 12 . doi : 10.1093/gigascience/giad101. ПМЦ 10716826 . ПМИД 38091509.
^ Ди Биази Л., Пиотто С. ARISE: Семантическая поисковая система на основе искусственного интеллекта . WIVACE2021.
^ Xu Z, Hao B (июль 2009 г.). «Обновление CVTree: недавно разработанная платформа филогенетического исследования с использованием композиционных векторов и целых геномов». Nucleic Acids Research . 37 (выпуск веб-сервера): W174–W178. doi :10.1093/nar/gkp278. PMC 2703908. PMID 19398429 .
^ Cheng J, Cao F, Liu Z (май 2013 г.). «AGP: многометодный веб-сервер для филогении генома без выравнивания». Молекулярная биология и эволюция . 30 (5): 1032–1037. doi : 10.1093/molbev/mst021 . PMC 7574599. PMID 23389766 .
^ Höhl M, Rigoutsos I, Ragan MA (февраль 2007 г.). «Оценка филогенетического расстояния на основе шаблонов и реконструкция дерева». Evolutionary Bioinformatics Online . 2 : 359–375. arXiv : q-bio/0605002 . Bibcode : 2006q.bio.....5002H. PMC 2674673. PMID 19455227 .
^ Wang Y, Liu L, Chen L, Chen T, Sun F (2 января 2014 г.). "Сравнение метатранскриптомных образцов на основе частот k-кортежей". PLOS ONE . 9 (1): e84348. Bibcode :2014PLoSO...984348W. doi : 10.1371/journal.pone.0084348 . PMC 3879298 . PMID 24392128.
^ "Модуль микробной геномики CLC". QIAGEN Bioinformatics . 2019.
^ Pratas D, Silva JM (январь 2021 г.). «Стойкие минимальные последовательности SARS-CoV-2». Биоинформатика . 36 (21): 5129–5132. doi : 10.1093/bioinformatics/btaa686 . PMC 7559010. PMID 32730589 .