Поиск мотивов растений - Planted motif search

В области вычислительная биология, а поиск мотивов растений (ПМС), также известный как (л, д) -мотивный поиск (LDMS) - это метод определения сохраненных мотивы в пределах набора нуклеиновая кислота или же пептидные последовательности.

ПМС известен как НП-полный. В временные сложности большинство алгоритмов поиска мотивов экспоненциально зависят от размера алфавита и л. Проблема ПМС была впервые представлена ​​Кейчем и Певзнером.^[1]

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

Описание

Задачу поиска можно резюмировать следующим образом:

На входе n строк (s₁, с₂,…, С_п) длины m из алфавита Σ и двух целых чисел l и d. Найдите все строки x такие, что | x | = l и каждая входная строка содержит хотя бы один вариант x в Расстояние Хэмминга не более d. Каждый такой x называется мотивом (l, d).

Например, если входными строками являются GCGCGAT, CACGTGA и CGGTGCC; л = 3 и d = 1, то интересный мотив - GGT. Обратите внимание, что первая входная строка имеет GAT как подстрока, вторая входная строка имеет CGT как подстроку, а третья входная строка имеет GGT как подстроку. GAT - это вариант GGT, который находится в пределах расстояния Хэмминга 1 от GGT и т. Д. Варианты мотива, которые встречаются во входных строках, называйте экземплярами мотива. Например, GAT - это экземпляр мотива GGT, который встречается в первой входной строке.

Ноль или больше (л, d) мотивы содержатся в любом заданном наборе входных строк. Многие из известных алгоритмов PMS считают Нити ДНК для которого Σ = {G, C, T, A}. Существуют алгоритмы которые также имеют дело с белковыми нитями. Проблема ПМС также известна как (л, d) проблема поиска мотива (LDMS).

Обозначение

Следующее математическая запись часто используется для описания алгоритмов PMS.

Предположим, что S = {s₁, с₂, с₃,…, С_п} - заданный набор входных строк из алфавита Σ. An л-mer любой строки - это не что иное, как подстрока строки длины л. Позволять d_ЧАС(а, б) стоять за Расстояние Хэмминга между любыми двумя л-меры а и б. Позволять а быть л-мер и s быть входной строкой. Тогда пусть d_ЧАС(в качестве) обозначают минимальное расстояние Хэмминга между а и любой л-мер б из s. Если а есть ли л-мер и S набор входных строк, тогда пусть d_ЧАС(в качестве) стенд для макс_sєSd_ЧАС(в качестве). Позволять ты быть любым л-мер. Затем d-окрестности ты, (обозначается как B_d(u)), есть не что иное, как совокупность всех л-меры v такой, что d_ЧАС(u, v) ≤ d. Другими словами, B_d(u) = {v: d_ЧАС(u, v) ≤d}. См. Любой такой л-мер v как d-сосед ты. B_d(х, у) используется для обозначения общего d-окрестности Икс и у, куда Икс и у два л-меры. B_d(х, у) это не что иное, как набор всего л-меры, находящиеся на расстоянии d от обоих Икс и у. По аналогии, B_d(х, у, г)и т. д. могут быть определены.

Алгоритмы

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

Приблизительный

Примеры аппроксимационные (или эвристические) алгоритмы включить случайную проекцию,^[2] Узор^[3] МУЛЬТИПРОФИЛЕР,^[1] КОНСЕНСУС,^[4] и ProfileBranching.^[3] Экспериментально продемонстрировано, что эти алгоритмы работают хорошо.

Случайная проекция

Алгоритм^[2] основан на случайных прогнозах. Пусть мотив M интересно быть л-мер и C быть собранием всех л-меры из всех п входные строки. Алгоритм проецирует эти л-меры вместе k случайно выбранные позиции (для некоторого подходящего значения k). Проекция каждого л-mer можно рассматривать как целое число. Прогнозируемые значения (которые k-mers) сгруппированы в соответствии с их целочисленными значениями. Другими словами, хешировать все л-меры, использующие k-мер любого л-mer в качестве его хэш-значения. Все л-меры с одинаковым значением хеш-функции попадают в одну и ту же хеш-корзину. Поскольку экземпляры любых (л, d) похожи друг на друга, многие из этих экземпляров попадут в одно ведро. Обратите внимание, что Расстояние Хэмминга между любыми двумя экземплярами (л, d) мотив не более 2d. Ключевая идея этого алгоритма - изучить те сегменты, в которых имеется большое количество л-меры в них. Для каждого такого ведра алгоритм максимизации ожидания (EM) используется для проверки наличия (л, d) можно найти с помощью л-меры в ведре.

Ветвление образца

Этот алгоритм^[3] это алгоритм локального поиска. Если ты есть ли л-мер, то есть ${\displaystyle {\tbinom {l}{d}}3^{d}}$ л-меры, которые d-соседи ты, для цепочек ДНК. Этот алгоритм начинается с каждого л-мер ты во вводе ищет соседей ты, оценивает их соответствующим образом и выводит соседа с лучшим результатом.

Точный

Известно много точных алгоритмов решения проблемы PMS. Примеры включают в себя (Martinez 1983),^[5] (Brazma, et al. 1998),^[6] (Галас и др., 1985),^[7] (Sinha и др., 2000),^[8] (Staden 1989),^[9] (Tompa 1999),^[10] (Helden и др., 1998 г.)^[11] (Раджасекаран и др.),^[12] (Давила и Раджашекаран, 2006 г.),^[13] (Давила, Балла и Раджасекаран, 2006 г.),^[14] Голосование^[15] и РИЗОТТО.^[16]

WINNOWER и SP-STAR

Алгоритм WINNOWER^[17] это эвристический алгоритм и работает он следующим образом. Если А и B два экземпляра одного и того же мотива в двух разных входных строках, тогда расстояние Хэмминга между А и B не больше 2d. Можно показать, что ожидаемое расстояние Хэмминга между А и B является ${\displaystyle 2d-{\tfrac {4d^{2}}{3l}}}$. WINNOWER создает коллекцию C из всех возможных л-меры на входе. График G (V, E) построен, в котором каждый л-мер C будет узлом. Два узла ты и v в грамм соединены ребром тогда и только тогда, когда расстояние Хэмминга между ты и v не больше 2d и они поступают из двух разных входных строк.

Если M является (л, d) мотив и если M₁, M₂, …, и M_п являются экземплярами M во входных строках, то очевидно, что эти экземпляры сформируют клика в грамм. Алгоритм WINNOWER состоит из двух этапов. На первом этапе выявляются крупные клики в грамм. На втором этапе каждая такая клика исследуется, чтобы увидеть, можно ли выделить из этой клики мотив. КЛИКА проблема в том несговорчивый, WINNOWER использует эвристику для решения CLIQUE. Он итеративно создает клики все большего и большего размера. Если N = мин, то время работы алгоритма равно ${\displaystyle O(N^{2d+1})}$. Этот алгоритм работает в разумные сроки на практике, особенно для небольших значений d.Еще один алгоритм называется SP-STAR,^[17] быстрее, чем WINNOWER, и использует меньше памяти. Алгоритм WINNOWER обрабатывает все грани грамм одинаково, не различая края на основе сходства. SP-STAR получает л-меры C а также края грамм соответствующим образом и, следовательно, удаляет больше ребер, чем WINNOWER за итерацию.

(Бейли и Элкан, 1994)^[18] использует алгоритмы максимизации ожидания, в то время как выборка Гиббса используется (Лоуренс и др., 1993).^[19] МУЛЬТИПРОФИЛЕР^[1] ЦМем,^[20] также известны алгоритмы PMS.

Серия PMS

За последнее десятилетие в лаборатории МГТУ была разработана серия алгоритмов с PMS в качестве префикса. Раджашекаран. Некоторые из этих алгоритмов описаны ниже.

PMS0

PMSo^[12] работает следующим образом. Позволять s₁, s₂, …, s_п быть заданным набором входных строк, каждая длиной м. Позволять C быть собранием л-меры в s₁. Пусть C '= ∪_u∈CB_d(ты). Для каждого элемента v из C ' проверьте, является ли это действительным (л, d) -мотив или нет. Учитывая л-мер v, проверка правильности (л, d) -мотив или нет могут быть выполнены в O (млн) время. Таким образом, время выполнения PMS0, предполагая размер алфавита 4, равно ${\displaystyle O(m^{2}nl{\tbinom {l}{d}}3^{d})}$.

PMS1

Этот алгоритм^[12] основан на радиксная сортировка и имеет следующие шаги.

1. Создайте набор всех л-mers в каждой строке ввода. Позволять C_я соответствуют л-меры s_я, для 1≤я≤п.
2. Для каждого л-мер ты в C_я (1 < я < п), генерировать B_d(ты). Позволять L_я быть набором всех этих соседей (соответствующих всем л-меры s_я).
3. Сортировать L_я (используя сортировку по основанию) и устраните любые дубликаты.
4. Вычислить:${\displaystyle \bigcap _{i=1}^{n}L_{i}.}$. Это можно сделать, объединив списки L₁, L₂, …, L_п. Все л-меры в этом пересечении действительны (л, d) мотивы.

PMS2

Пусть мотив M представляющий интерес быть длинным л. Если M встречается в каждой входной строке, тогда любой подстрока из M также встречается в каждой строке ввода. Здесь возникновение означает появление на расстоянии Хэмминга d. Отсюда следует, что есть не менее л-k+1 строка каждой длины k (за k ≤ л), так что каждый из них встречается в каждой входной строке.

Позволять Q быть собранием k-меры в M. Обратите внимание, что в каждой строке ввода s_я, будет хотя бы одна позиция я_j так что k-мер Q происходит начиная с я_j. Другой k-мер Q происходит начиная с я_j +1 и так далее, с последним k-мер происходит в я_j + l - k. An л-mer можно получить, объединив эти k-меры, возникающие начиная с каждого такого я_j.

PMS2^[12] работает следующим образом. На первом этапе найдите все (k, d) мотивы присутствуют во всех входных строках (для некоторого подходящего значения k<л). На втором этапе ищите (л-k+1) из них (k, d) мотивы, которые появляются, начиная с последовательных позиций в каждой из входных строк. Из каждой такой коллекции (л-k+1) (k, d) -мотивы, л-mer может быть сгенерирован (если возможно). Каждый такой л-мер - кандидат (л, d) -мотив. Для каждого мотива-кандидата проверьте, является ли он (л, d) -мотив или нет в O (млн) время. Этот л-mer возвращается как результат, если это (л, d) -мотив.

PMS3

Этот алгоритм^[12] позволяет обрабатывать большие значения d. Позволять d’=d/ 2. Позволять M быть мотивом, который можно найти с помощью |M|=л=2л’Для некоторого целого числа л'. Позволять M₁ относятся к первой половине M и M₂ быть следующей половиной. Позволять s= а₁а₂… А_м быть одной из входных строк. M встречается в каждой строке ввода. Пусть возникновение M (на расстоянии Хэмминга d) в s начать с позиции я. Позволять s’=а_яа_{я + 1}… А_{я + л’-1} и s’’ =а_{я + л}'… А_{я + л-1}Ясно, что либо расстояние Хэмминга между M₁ и s’Не более d'Или расстояние Хэмминга между M₂ и s’’ Не более d'. Либо M₁ или же M₂ встречается в каждой входной строке на расстоянии Хэмминга не более d'. В результате как минимум в п'Строки (где п’ = п/ 2) либо M₁ или же M₂ происходит с расстоянием Хэмминга не более dАлгоритм сначала получает все (л’, d’) -Мотивы, которые встречаются как минимум в п/ 2 входных строк. Затем он использует эти мотивы и вышеприведенные наблюдения, чтобы идентифицировать все (л, d) -мотивы присутствуют во входных строках.

PMSPrune

Этот алгоритм вводит древовидная структура для кандидатов в мотив и использует алгоритм ветвей и границ чтобы уменьшить пространство поиска.^[21] Позволять S = {s₁, с₂,…, С_п} быть заданным набором входных строк. PMSprune следует той же стратегии, что и PMS0: для каждого л-мер у в s₁, он генерирует множество соседей у и для каждого из них проверяет, является ли это мотивом. Некоторые ключевые шаги в алгоритме:

1. Это порождает d-соседство каждого л-мер у в s₁ используя дерево высоты d. В корне этого дерева будет у. Каждый л-мер, находящийся на расстоянии 1 от у будет узлом в дереве, который находится на расстоянии 1 от корня; каждый л-мер, находящийся на расстоянии 2 от у будет узлом в дереве, который находится на расстоянии 2 от корня; и так далее. При посещении узла в этом дереве проверьте, соответствует ли соответствующий л-mer - это (л, d) -мотив. Т.е., если л-мер это Икс, проверить, если d_ЧАС(х, S)≤d. Если да, выведите это л-мер. В любом случае переходите к следующему узлу в дереве. Это дерево исследуется в сначала глубина манера.
2. Если каждый узел в дереве посещается для каждого л-мер у в s₁, то время работы PMSPrune будет не меньше, чем у PMS0. PMSPrune использует некоторые условия отсечения для отсечения поддеревьев, в которых не может быть никаких мотивов.
3. Для л-мер Икс, что соответствует узлу в поддереве высотой час, алгоритм использует значение d_ЧАС(х, S) и час обрезать потомков Икс.
4. PMSPrune рассчитывает стоимость d_ЧАС(х, S) для узлов (Икс) в дереве поэтапно с учетом способа создания окрестности.

PMS4

PMS4^[22] - это метод, который можно использовать для ускорения любого алгоритма проблемы PMS. Во многих из вышеперечисленных алгоритмов есть две фазы. На первом этапе мы придумываем набор мотивов-кандидатов, а на втором этапе проверяем для каждого мотива-кандидата, является ли он допустимым (л, d) -мотив. Для каждого мотива-кандидата требуется O (млн) пора проверить, правильный это мотив или нет. PMS4 использует аналогичную двухфазную стратегию. Эти этапы объясняются ниже. Пусть A - любой алгоритм PMS.

1. Запустите алгоритм A на k входные строки (где k < п). Оптимальное значение k можно определить эмпирически. В k струны можно выбирать разными способами. Например, они могли быть первыми k строки, случайные k струны и так далее. Позволять C быть сборником (л, d) -мотивы, найденные в этих k струны. Четко, C является надмножеством (л, d) -мотивы, присутствующие в п данные входные строки.
2. для каждого л-мер v в C делать

Проверить, если v допустимый мотив в O (млн) время. Если да, выведите v.

PMS5 и PMS6

PMS5^[23] является расширением PMS0. Если S = {s₁, s₂, …, s_п} - это набор строк (не обязательно одинаковой длины), пусть ${\displaystyle M_{l}^{d}(S)}$ обозначим (л, d) -мотивы присутствуют в S. Позволять S’ = {s₂, с₃,…, С_п}. PMS5 вычисляет (л, d) -мотивы S в качестве ${\displaystyle \bigcup _{L\in s_{1}}M_{l}^{d}(L,S^{'})}$. Здесь L относится к л-мер.

Одним из ключевых шагов алгоритма является подпрограмма вычислить общие d-окрестности трех л-меры. Позволять Икс, у, z быть любыми тремя л-меры. Вычислить B_d(х, у, г), PMS5 представляет B_d(Икс) как дерево Т_d(Икс). Каждый узел в этом дереве представляет собой л-мер в B_d(Икс). Корень Т_d(Икс) стоит за л-мер х. Т_d(Икс) имеет глубину _d. Узлы Т_d(Икс) пройдены в в глубину манера. Узел и л-mer, который он представляет, может использоваться как взаимозаменяемые. Пока дерево пройденный, любой узел т будет выводиться, если т в ${\displaystyle B_{d}(y)\bigcap B_{d}(z)}$. Когда любой узел т посещается, проверьте, есть ли потомок т ' из т такой, что т ' в ${\displaystyle B_{d}(y)\bigcap B_{d}(z)}$. Подрезать поддерево укорененный в т если такого потомка нет. В PMS5 проблема проверки наличия т имеет потомков в ${\displaystyle B_{d}(y)\bigcap B_{d}(z)}$ сформулирован как целочисленная линейная программа (ИЛП) по десяти переменным. Эта ILP решается за O (1) раз. Решение экземпляров ILP выполняется как предварительная обработка step, и результаты сохраняются в таблице поиска.

Алгоритм PMS6^[24] является расширением PMS5, которое улучшает этап предварительной обработки, а также использует эффективные хеширование методы для хранения таблиц поиска. В результате он обычно быстрее, чем PMS5.

Шибдас Бандйопадхьяй, Сартадж Сахни, Сангутевар Раджасекаран, «PMS6: быстрый алгоритм для обнаружения мотивов», iccabs, стр. 1-6, 2012 2-я Международная конференция IEEE по вычислительным достижениям в биологических и медицинских науках, 2012 г.

qPMSPrune и qPMS7

Учитывая набор S={s₁, с₂,…, С_п} строк и целых чисел л, d, и q, an (л, д, д) -мотив определяется как строка M длины л что происходит по крайней мере в q из п входные строки на расстоянии Хэмминга d. QPMS (Поиск мотивов кворума) проблема состоит в том, чтобы найти все (л, д, д) -мотивы присутствуют во входных строках. Проблема qPMS отражает природу мотивов более точно, чем проблема PMS, потому что на практике некоторые мотивы могут не иметь экземпляров мотива во всех входных строках. Любой алгоритм для решения проблемы qPMS (когда q ≠ п) обычно именуется с префиксом `q '. qPMSPrune - один из первых алгоритмов, решающих эту версию проблемы PMS.^[21] qPMSPrune использует следующий факт: если M есть ли (л, д, д) -мотив входных строк s₁, с₂,…, С_п, то существует я (с 1 ≤ я ≤ п – q + 1) и л-мер ${\displaystyle {x\in s_{i}}}$ такой, что M в B_d(Икс) и M является (l, d, q-1) -мотив входных строк без учета s_я. Алгоритм обрабатывает каждое s_я, 1≤ я ≤ п. При обработке s_я, он считает все л-мер Икс из s_я. При рассмотрении Икс, он строит B_d(Икс) и определяет элементы B_d(Икс) которые (л, д, д-1) мотивы (по отношению к входным строкам, кроме s_я). B_d(Икс) представлен в виде дерева с Икс как корень. Это дерево будет пройдено в сначала глубина манера. Алгоритм не проходит по всему дереву. Некоторые поддеревья обрезаются с использованием эффективных условий обрезки. В частности, поддерево удаляется, если можно сделать вывод, что ни один из узлов в этом поддереве не несет интересующий мотив.

Алгоритм qPMS7^[25] является расширением qPMSPrune. В частности, он основан на следующем наблюдении: если M есть ли (л, д, д) -мотив входных строк s₁, с₂,…, С_п, то существует 1 ≤ я ≠ j ≤ п и л-мер ${\displaystyle x\in s_{i}}$ и л-мер ${\displaystyle y\in s_{j}}$ такой, что M в ${\displaystyle B_{d}(x)\bigcap B_{d}(y)}$ и M является (л, д, д-2) -мотив входных строк без учета s_я и s_j. Алгоритм рассматривает все возможные пары (я, j), 1≤ я, j ≤ п и я ≠ j. Для любой пары (я, j), всевозможные пары л-меры (х, у) считается (где Икс из s_я и у из s_j). Учитывая любые Икс и у, алгоритм идентифицирует все элементы ${\displaystyle B_{d}(x)\bigcap B_{d}(y)}$ которые (л, д, д-2) мотивы (по отношению к входным строкам, кроме s_я и s_j). An ациклический граф используется для представления и изучения ${\displaystyle B_{d}(x)\bigcap B_{d}(y)}$. Назовите этот график грамм_d(х, у). грамм_d(х, у) сначала проходит по глубине. Как и в qPMSPrune, qPMS7 также использует некоторые условия сокращения для сокращения подграфов грамм_d(х, у).

РИЗОТТО

РИЗОТТО^[16] нанимает суффиксное дерево определить (л, д) -мотивы. Он чем-то похож на PMS0. Для каждого л-мер в s₁, он генерирует d-соседство и для каждого л-mer в этом районе он проходит через дерево суффиксов, чтобы проверить, л-mer - это (л, д) -мотив. Голосование^[15] похож на PMS1. Вместо использования поразрядной сортировки он использует хеширование для вычисления L_яИ их перекрестки.

Относительная производительность

Алгоритмы PMS обычно тестируются на случайных контрольных данных, сгенерированных следующим образом: двадцать строк каждая длиной 600 генерируются случайным образом из интересующего алфавита. Мотив M также генерируется случайным образом и устанавливается в каждую из входных цепочек на расстоянии Хэмминга, равном d. Экземпляры мотивов также генерируются случайным образом. Некоторые экземпляры (л, д) -мотивы были определены как испытывающий. Для данного значения л, экземпляр (л, д) называется сложным, если d - наименьшее целое число, для которого ожидаемое количество (л, д) -мотивов, возникающих случайно (помимо посаженного) - один или несколько. Например, следующие примеры являются сложными: (9, 2), (11, 3), (13, 4), (15, 5), (17, 6), (19, 7) и т. Д. Алгоритмы PMS обычно показаны только для сложных случаев. Ниже приводится таблица сравнения времени различных алгоритмов PMS на сложных экземплярах последовательностей ДНК для особого случая. Эта таблица взята из статьи qPMS7.^[25] В этой таблице сравнивается несколько алгоритмов: qPMSPrune,^[21] qPMSPruneI,^[25] Пампа,^[26] Голосование,^[15] РИЗОТТО,^[16] PMS5,^[23] PMS6,^[24] qPMS7.^[25]

В следующей таблице алфавит ∑ = {А,C,грамм,Т}, п=20, м= 600, и q=п=20.

СРАВНЕНИЕ ПО ВРЕМЕНИ РАЗЛИЧНЫХ АЛГОРИТМОВ PMS

Алгоритм	(13,4)	(15,5)	(17,6)	(19,7)	(21,8)	(23,9)
qPMS7	47 с	2,6 м	11 мес.	0,9 ч	4,3 ч	24 ч
PMS6	67 с	3,2 м	14 м	1,16 ч	5,8 часов	-
PMS5	117 с	4,8 м	21,7 м	1,7 ч	9,7 ч	54 ч
qPMSPruneI	17 с	2,6 м	22,6 м	3,4 ч	29 часов	-
Пампа	35 с	6 мес.	40 кв.м.	4.8 ч	-	-
qPMSPrune	45 с	10,2 м	78,7 м	15,2 ч	-	-
Голосование	104 с	21,6 м	-	-	-	-
РИЗОТТО	772 с	106 кв.м.	-	-	-	-

Рекомендации

1. Keich, U .; Певзнер, П. А. (октябрь 2002 г.). «Поиск мотивов в сумеречной зоне». Биоинформатика. 18 (10): 1374–1381. Дои:10.1093 / биоинформатика / 18.10.1374. PMID  12376382.
2. Buhler, J .; Томпа, М. (2002). «Поиск мотивов по случайным проекциям». J. Comput. Биол. 9 (2): 225–242. CiteSeerX  10.1.1.26.2491. Дои:10.1089/10665270252935430. PMID  12015879.
3. Цена, А .; Ramabhadran, S .; Певзнер, П. А. (октябрь 2003 г.). «Обнаружение тонких мотивов путем разветвления от сэмплов струн». Биоинформатика. 19 Дополнение 2: ii149–55. Дои:10.1093 / биоинформатика / btg1072. PMID  14534184.
4. Герц, Г. З .; Стормо, Г. Д. (1999). «Идентификация образцов ДНК и белков со статистически значимым выравниванием нескольких последовательностей». Биоинформатика. 15 (7–8): 563–77. Дои:10.1093 / биоинформатика / 15.7.563. PMID  10487864.
5. Мартинес, Х. М. (июль 1983 г.). «Эффективный метод поиска повторов в молекулярных последовательностях». Нуклеиновые кислоты Res. 11 (13): 4629–4634. Дои:10.1093 / nar / 11.13.4629. ЧВК  326069. PMID  6866775.
6. Brazma, A .; Йонассен, I .; Vilo, J .; Укконен, Э. (ноябрь 1998 г.). «Прогнозирование регуляторных элементов генов in silico в геномном масштабе». Genome Res. 8 (11): 1202–1215. Дои:10.1101 / гр.8.11.1202. ЧВК  310790. PMID  9847082.
7. Галас, Д. Дж .; Eggert, M .; Уотерман, М. С. (ноябрь 1985 г.). «Строгие методы распознавания образов для последовательностей ДНК. Анализ промоторных последовательностей из Escherichia coli». J. Mol. Биол. 186 (1): 117–128. Дои:10.1016/0022-2836(85)90262-1. PMID  3908689.
8. Sinha, S .; Томпа, М. (2000). «Статистический метод поиска сайтов связывания факторов транскрипции». Proc Int Conf Intell Syst Mol Biol. 8: 344–354. PMID  10977095.
9. Стаден, Р. (октябрь 1989 г.). «Методы обнаружения новых мотивов в последовательностях нуклеиновых кислот». Comput. Appl. Biosci. 5 (4): 293–8. Дои:10.1093 / биоинформатика / 5.4.293. PMID  2684350.
10. Томпа, М. (1999). «Точный метод поиска коротких мотивов в последовательностях с приложением к проблеме сайта связывания рибосом». Proc Int Conf Intell Syst Mol Biol: 262–271. PMID  10786309.
11. van Helden, J .; Андре, Б.; Колладо-Видес, Дж. (Сентябрь 1998 г.). «Извлечение регуляторных сайтов из вышележащей области генов дрожжей с помощью компьютерного анализа частот олигонуклеотидов». J. Mol. Биол. 281 (5): 827–842. CiteSeerX  10.1.1.18.6830. Дои:10.1006 / jmbi.1998.1947. PMID  9719638.
12. Rajasekaran, S .; Balla, S .; Хуанг, К. Х. (октябрь 2005 г.). «Точные алгоритмы решения задач с посадочными мотивами». J. Comput. Биол. 12 (8): 1117–1128. CiteSeerX  10.1.1.549.5547. Дои:10.1089 / cmb.2005.12.1117. PMID  16241901.
13. Davila, J .; Раджасекаран, С. (2006). Расширение ветвления шаблона для обработки сложных экземпляров. Биоинформатика и биоинжиниринг. С. 65–69. Дои:10.1109 / BIBE.2006.253317. ISBN  978-0-7695-2727-7. S2CID  17562470.
14. Davila, J .; Balla, S .; Раджасекаран, S (2006). «Пространственно-временные алгоритмы поиска растительных мотивов». Proc. 6-я Международная конференция по вычислительной науке (ICCS 2006) / 2-й Международный семинар по биоинформатическим исследованиям и приложениям (IWBRA 2006) LNCS 3992: 822–829. CiteSeerX  10.1.1.94.4572.
15. Чин, Ф.Я.; Люнг, Х.С.М. (2005). Алгоритмы голосования для выявления длинных мотивов. Труды Третьей Азиатско-Тихоокеанской конференции по биоинформатике (APBC). С. 261–271. CiteSeerX  10.1.1.123.2457. Дои:10.1142/9781860947322_0026. ISBN  978-1-86094-477-2.
16. Pisanti, N .; Carvalho, A .; Марсан, Л .; Сагот, М. Ф. (2006). «Ризотто: быстрое извлечение несовпадающих мотивов». Материалы 7-го латиноамериканского симпозиума по теоретической информатике: 757–768. CiteSeerX  10.1.1.60.1028.
17. Певзнер, П. А .; Зе, С. Х. (2000). «Комбинаторные подходы к поиску тонких сигналов в последовательностях ДНК». Proc Int Conf Intell Syst Mol Biol. 8: 269–278. PMID  10977088.
18. Bailey, T. L .; Элкан, К. (1994). «Подбор модели смеси путем максимизации ожиданий для обнаружения мотивов в биополимерах». Proc Int Conf Intell Syst Mol Biol. 2: 28–36. PMID  7584402.
19. Lawrence, C.E .; Altschul, S. F .; Богуски, М. С .; Liu, J. S .; Neuwald, A. F .; Вуттон, Дж. К. (октябрь 1993 г.). «Обнаружение тонких сигналов последовательности: стратегия выборки Гиббса для множественного выравнивания». Наука. 262 (5131): 208–214. Дои:10.1126 / science.8211139. PMID  8211139.
20. Bailey, T. L .; Элкан, Чарльз (январь 1995 г.). «Неконтролируемое изучение множества мотивов в биополимерах с использованием максимизации ожидания». Машинное обучение. 21 (1–2): 51–80. Дои:10.1007 / BF00993379.
21. Davila, J .; Balla, S .; Раджасекаран, С. (2007). «Быстрые и практичные алгоритмы поиска растительных (л, г) мотивов». IEEE / ACM Trans Comput Biol Bioinform. 4 (4): 544–552. Дои:10.1109 / TCBB.2007.70241. PMID  17975266. S2CID  15212174.
22. Rajasekaran, S .; Динь, Х. (2011). «Техника ускорения алгоритмов поиска (l, d) -мотивов». BMC Res Примечания. 4: 54. Дои:10.1186/1756-0500-4-54. ЧВК  3063805. PMID  21385438.
23. Dinh, H .; Rajasekaran, S .; Кундети, В. К. (2011). «PMS5: эффективный точный алгоритм для задачи поиска (ℓ, d) -мотива». BMC Биоинформатика. 12: 410. Дои:10.1186/1471-2105-12-410. ЧВК  3269969. PMID  22024209.
24. Bandyopadhyay, S .; Sahni, S .; Раджасекаран, С. (2012). PMS6: быстрый алгоритм обнаружения мотивов. 2-я Международная конференция IEEE по вычислительным достижениям в биологических и медицинских науках. С. 1–6. Дои:10.1109 / ICCABS.2012.6182627. ISBN  978-1-4673-1321-6. ЧВК  3744182. PMID  23959399.
25. Dinh, H .; Rajasekaran, S .; Давила, Дж. (2012). Брусич, Владимир (ред.). «qPMS7: быстрый алгоритм для поиска (ℓ, d) -мотивов в ДНК и белковых последовательностях». PLOS ONE. 7 (7): e41425. Дои:10.1371 / journal.pone.0041425. ЧВК  3404135. PMID  22848493.
26. Davila, J .; Balla, S .; Раджасекаран, С. (2007). «Пампа: улучшенный алгоритм ветвей и границ для поиска мотивов растений (l, d)». Технический отчет. CiteSeerX  10.1.1.93.6500.

внешняя ссылка

• Rajasekaran, S .; Динь, Х. "Поиск мотивов PMS". Университет Коннектикута. Архивировано из оригинал на 2011-05-15.
• Rajasekaran, S .; Динь, Х. "Паноптический поиск мотивов". Университет Коннектикута. Архивировано из оригинал на 02.08.2011.