Поиск посаженных мотивов

В области вычислительной биологии поиск посаженных мотивов (PMS), также известный как поиск ( l, d )-мотивов (LDMS), представляет собой метод идентификации консервативных мотивов в наборе последовательностей нуклеиновых кислот или пептидов .

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

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

Описание

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

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

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

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

Обозначения

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

Предположим, что S = { s ₁ , s ₂ , s ₃ , ..., s _n } — заданный набор входных строк из алфавита Σ. - мер l любой строки — это не что иное, как подстрока строки длины l . Пусть d _H (a, b) обозначает расстояние Хэмминга между любыми двумя l -мерами a и b . Пусть a — l - мер, а s — входная строка. Тогда пусть d _H (a, s) обозначает минимальное расстояние Хэмминга между a и любым l -мером b из s . Если a — любой l -мер и S — набор входных строк, то пусть d _H (a, S) обозначает max _sєS d _H (a, s) . Пусть ты будешь любым л -мером. Тогда d -окрестность точки u (обозначаемая как B _d (u) ) — это не что иное, как множество всех l -меров v таких, что d _H (u, v) ⩽ d . Другими словами, B _d (u)={v: d _H (u, v)≤d} . Любой такой l -mer v соседом будем называть d - u . B _d (x, y) используется для обозначения общей d -окрестности x и y , где x и y — два l -мера. B _d (x, y) — это не что иное, как набор всех l -меров, находящихся на расстоянии d от x и y . Аналогичным образом B _d (x, y, z) можно определить и т. д.

Алгоритмы

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

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

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

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

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

Ветвление шаблона

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

Точный

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

ПОБЕДИТЕЛЬ и SP-STAR

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

Если M является мотивом ( , d ) и если , _M1 M2 , _{во входных} ... и Mn _M являются экземплярами l очевидно, эти экземпляры образуют клику в G. строках, то , Алгоритм WINNOWER состоит из двух этапов. На первом этапе он идентифицирует большие клики G. в На втором этапе каждая такая клика исследуется на предмет того, можно ли извлечь из этой клики мотив. Поскольку CLIQUE проблема неразрешима , WINNOWER использует эвристику для решения CLIQUE. Он итеративно строит клики все большего и большего размера. Если N = mn , то время работы алгоритма равно $O(N^{2d+1})$ . На практике этот алгоритм работает за разумное время, особенно для небольших значений d . Другой алгоритм под названием SP-STAR, ^[17] работает быстрее, чем WINNOWER, и использует меньше памяти. Алгоритм WINNOWER обрабатывает все ребра G одинаково, не делая различий между ребрами на основе сходства. SP-STAR соответствующим образом оценивает l -меры C , а также ребра G и, следовательно, исключает больше ребер, чем WINNOWER, за итерацию.

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

серия ПМС

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

ПМС0

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

ПМС1

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

Сгенерируйте набор всех l -меров в каждой входной строке. Пусть C _i соответствует l -мерам s _i , для 1妻 i ⩽ n .
Для каждого l -мера u в C _i (1 < i < n ) сгенерируйте B _d ( u ). Пусть L _i — совокупность всех этих соседей (соответствующая всем l -мерам s _i ).
Отсортируйте L _i (используя поразрядную сортировку) и удалите все дубликаты.
Вычислить: $\bigcap _{i=1}^{n}L_{i}.$ . Это можно сделать путем слияния списков L ₁ , L ₂ , ..., L _n . Все l -меры в этом пересечении являются допустимыми ( l , d ) мотивами.

ПМС2

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

Пусть Q — набор k в M. - меров Обратите внимание, что в каждой входной строке s _i будет хотя бы одна позиция i _j такая, что k -мер Q встречается, начиная с i _j . Еще один k -мер Q возникает, начиная с i _j +1 и так далее, причем последний k -мер приходится на i _j + l – k . L -меров, которые встречаются, начиная с -мер может быть получен путем объединения этих k каждого такого i _j .

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

ПМС3

Этот алгоритм ^[12] позволяет обрабатывать большие значения d . Пусть d′ = d /2. Пусть M — мотив, который можно найти с помощью | M |= l =2 l′ для некоторого целого числа l′ . Пусть M ₁ относится к первой половине M , а M ₂ — к следующей половине. Пусть s = a ₁ a ₂ ... _am — одна из входных строк. M встречается в каждой входной строке. Пусть появление M (в пределах расстояния Хэмминга d ) в s начинается с позиции i . Пусть s' = a _i a _i+1 ...a _i+l'-1 и s'' = a _i+l '...a _i+l-1 .

Ясно, что либо расстояние Хэмминга между M ₁ и s' не превосходит d', либо расстояние Хэмминга между M ₂ и s'' не превосходит d' . Либо M ₁ , либо M ₂ встречается в каждой входной строке на расстоянии Хэмминга не более d' . В результате как минимум в n' строках (где n' = n /2) встречается либо M ₁ , либо M ₂ с расстоянием Хэмминга не более d .

Алгоритм сначала получает все ( l′ , d′ )-мотивы, которые встречаются как минимум в n /2 входных строк. Затем он использует эти мотивы и приведенные выше наблюдения для идентификации всех ( l , d )-мотивов, присутствующих во входных строках.

PMSPrun

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

Он генерирует d -окрестность каждого l -мера y в s _1, используя дерево высоты d . Корень этого дерева будет иметь y . Каждый l -мер, находящийся на расстоянии 1 от y , будет узлом дерева, находящимся на расстоянии 1 от корня; каждый l -мер, находящийся на расстоянии 2 от y , будет узлом дерева, находящимся на расстоянии 2 от корня; и так далее. При посещении узла в этом дереве проверьте, является ли соответствующий l -мер ( l , d )-мотивом. Т.е., если l -мер равен x , проверьте, что d _H (x, S) ≤ d . Если да, выведите этот l -mer. В любом случае перейдите к следующему узлу дерева. Это дерево исследуется в первую очередь в глубину.
Если каждый узел в дереве посещается для каждого l -мера y в s ₁ , то время работы PMSPrune будет как минимум таким же, как и у PMS0. PMSPrune использует некоторые условия обрезки для обрезки поддеревьев, в которых не может быть никаких мотивов.
Для l -mer x , который соответствует узлу в поддереве высоты h , алгоритм использует значение d _H (x, S) и h для отсечения потомков x .
PMSPrune вычисляет значение d _H (x, S) для узлов ( x ) в дереве инкрементным способом, принимая во внимание способ генерации окрестности.

ПМС4

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

Запустите алгоритм A на k входных строках (где k < n ). Оптимальное значение k можно определить эмпирически. строк K можно выбрать разными способами. Например, это могут быть первые k строк, случайные k строк и т. д. Пусть C — совокупность ( l , d )-мотивов, найденных в этих k строках. Очевидно, что C является расширенным набором ( l , d )-мотивов, присутствующих в n заданных входных строках.
для каждого l -mer v в C do

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

ПМС5 и ПМС6

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

Одним из ключевых шагов алгоритма является подпрограмма вычисления общего d -окрестности трех l- меров. Пусть x , y , z — любые три l -мера. Чтобы вычислить B _d (x, y, z) PMS5 представляет B _d (x) как дерево T _d (x) . Каждый узел в этом дереве представляет l -мер в B _d (x) . Корень T _d (x) обозначает l -мер x. T _d (x) имеет глубину _d . Узлы T _d (x) проходятся в глубину . Узел и представляемый им l -мер могут использоваться взаимозаменяемо. дерева Во время обхода любой узел t будет выведен, если t находится в $B_{d}(y)\bigcap B_{d}(z)$ . любого узла t При посещении проверьте, существует ли потомок t' от t такой, что t' находится в $B_{d}(y)\bigcap B_{d}(z)$ . Сократите поддерево с корнем в t, если такого потомка нет. В PMS5 проблема проверки наличия у t какого-либо потомка, находящегося в $B_{d}(y)\bigcap B_{d}(z)$ формулируется как целочисленная линейная программа (ЦЛП) с десятью переменными. Эта ILP решается за время O(1). Решение экземпляров ILP выполняется на этапе предварительной обработки , а результаты сохраняются в справочной таблице.

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

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

qPMSPrune и qPMS7

Учитывая набор S = { s ₁ , s ₂ , ..., s _n } строк и целых чисел l , d и q , ( l, d, q )-мотив определяется как строка M длины l , который встречается как минимум в q из n входных строк в пределах расстояния Хэмминга d . Задача qPMS ( Quorum Planted Motif Search ) состоит в том, чтобы найти все ( l, d, q )-мотивы, присутствующие во входных строках. Проблема qPMS более точно отражает природу мотивов, чем проблема PMS, поскольку на практике некоторые мотивы могут не иметь экземпляров мотивов во всех входных строках. Любой алгоритм решения проблемы qPMS (когда q ≠ n ) обычно имеет префикс q . qPMSPrune — один из первых алгоритмов, решающих эту версию проблемы ПМС. ^[21] qPMSPrune использует следующий факт: если M — любой ( l, d, q )-мотив входных строк s ₁ , s ₂ , ..., s _n , то существует i (с 1 ≤ i ≤ n – q + 1) и l -мер ${x\in s_{i}}$ такой, что M находится в B _d (x) и M является ( l, d, q -1)-мотивом входных строк, исключая s _i . Алгоритм обрабатывает каждое s _i , 1≤ i ≤ n . При обработке s _i он учитывает каждый l -мер x из s _i . При рассмотрении x он создает B _d (x) и идентифицирует элементы B _d (x) , которые являются мотивами ( l, d, q -1) (относительно входных строк, отличных от s _i ). B _d (x) представляется в виде дерева с x корнем . Это дерево будет пройдено в глубину . Алгоритм не обходит все дерево. Некоторые поддеревья обрезаются с использованием эффективных условий обрезки. В частности, поддерево сокращается, если можно сделать вывод, что ни один из узлов этого поддерева не несет интересующего мотива.

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

РИЗОТТО

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

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

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

В следующей таблице алфавит Σ={ A , C , G , T }, n =20, m =600 и q = n =20.

СРАВНЕНИЕ ВРЕМЕНИ РАЗЛИЧНЫХ АЛГОРИТМОВ PMS
Алгоритм	(13,4)	(15,5)	(17,6)	(19,7)	(21,8)	(23,9)
qPMS7	47 с	2,6 м	11 м	0,9 ч.	4,3 ч.	24 часа
ПМС6	67 с	3,2 м	14 м	1,16 ч.	5,8 ч.	-
ПМС5	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 м	-	-	-	-

Ссылки

^ Перейти обратно: ^а ^б ^с Кейч, У.; Певзнер, Пенсильвания (октябрь 2002 г.). «Нахождение мотивов в сумеречной зоне» . Биоинформатика . 18 (10): 1374–1381. дои : 10.1093/биоинформатика/18.10.1374 . ПМИД 12376382 .
^ Перейти обратно: ^а ^б Бюлер, Дж.; Томпа, М. (2002). «Нахождение мотивов с помощью случайных проекций». Дж. Компьютер. Биол . 9 (2): 225–242. CiteSeerX 10.1.1.26.2491 . дои : 10.1089/10665270252935430 . ПМИД 12015879 .
^ Перейти обратно: ^а ^б ^с Прайс, А.; Рамабхадран, С.; Певзнер, Пенсильвания (октябрь 2003 г.). «Нахождение тонких мотивов путем разветвления образцов струн» . Биоинформатика . 19 (Приложение 2): ii149–55. doi : 10.1093/биоинформатика/btg1072 . ПМИД 14534184 .
^ Герц, Г.З.; Стормо, Джорджия (1999). «Идентификация структур ДНК и белков со статистически значимым выравниванием нескольких последовательностей» . Биоинформатика . 15 (7–8): 563–77. дои : 10.1093/биоинформатика/15.7.563 . ПМИД 10487864 .
^ Мартинес, HM (июль 1983 г.). «Эффективный метод поиска повторов в молекулярных последовательностях» . Нуклеиновые кислоты Рез . 11 (13): 4629–4634. дои : 10.1093/нар/11.13.4629 . ПМК 326069 . ПМИД 6866775 .
^ Бразма, А.; Йонассен, И.; Вило, Дж.; Укконен, Э. (ноябрь 1998 г.). «Прогнозирование регуляторных элементов генов in silico в геномном масштабе» . Геном Рез . 8 (11): 1202–1215. дои : 10.1101/гр.8.11.1202 . ПМК 310790 . ПМИД 9847082 .
^ Галас, диджей; Эггерт, М.; Уотерман, М.С. (ноябрь 1985 г.). «Строгие методы распознавания образов последовательностей ДНК. Анализ промоторных последовательностей Escherichia coli». Дж. Мол. Биол . 186 (1): 117–128. дои : 10.1016/0022-2836(85)90262-1 . ПМИД 3908689 .
^ Синха, С.; Томпа, М. (2000). «Статистический метод поиска сайтов связывания факторов транскрипции». Proc Int Conf Intell Syst Mol Biol . 8 : 344–354. ПМИД 10977095 .
^ Стаден, Р. (октябрь 1989 г.). «Методы обнаружения новых мотивов в последовательностях нуклеиновых кислот». Вычислить. Прил. Биосци . 5 (4): 293–8. дои : 10.1093/биоинформатика/5.4.293 . ПМИД 2684350 .
^ Томпа, М. (1999). «Точный метод поиска коротких мотивов в последовательностях с применением к проблеме сайта связывания рибосом». Proc Int Conf Intell Syst Mol Biol : 262–271. ПМИД 10786309 .
^ ван Хелден, Дж.; Андре, Б.; Кольядо-Видес, Дж. (сентябрь 1998 г.). «Извлечение регуляторных сайтов из вышележащей области генов дрожжей путем компьютерного анализа частот олигонуклеотидов». Дж. Мол. Биол . 281 (5): 827–842. CiteSeerX 10.1.1.18.6830 . дои : 10.1006/jmbi.1998.1947 . ПМИД 9719638 .
^ Перейти обратно: ^а ^б ^с ^д ^и Раджасекаран, С.; Балла, С.; Хуанг, Швейцария (октябрь 2005 г.). «Точные алгоритмы решения задач с посаженными мотивами». Дж. Компьютер. Биол . 12 (8): 1117–1128. CiteSeerX 10.1.1.549.5547 . дои : 10.1089/cmb.2005.12.1117 . ПМИД 16241901 .
^ Давила, Дж.; Раджасекаран, С. (2006). «Расширение ветвления шаблонов для обработки сложных экземпляров». Шестой симпозиум IEEE по биоинформатике и биоинженерии (BIBE'06) . стр. 65–69. дои : 10.1109/BIBE.2006.253317 . ISBN 978-0-7695-2727-7 . S2CID 17562470 . {{cite book}}: |journal= игнорируется ( помогите )
^ Давила, Дж.; Балла, С.; Раджасекаран, С. (2006). «Эффективные по пространству и времени алгоритмы поиска посаженных мотивов». Учеб. 6-я Международная конференция по вычислительной науке (ICCS 2006) / 2-й Международный семинар по исследованиям и приложениям в области биоинформатики (IWBRA 2006) LNCS 3992 : 822–829. CiteSeerX 10.1.1.94.4572 .
^ Перейти обратно: ^а ^б ^с Чин, БЮЛ ; Люнг, HCM (2005). «Алгоритмы голосования для обнаружения длинных мотивов». Материалы 3-й Азиатско-Тихоокеанской конференции по биоинформатике . стр. 261–271. CiteSeerX 10.1.1.123.2457 . дои : 10.1142/9781860947322_0026 . ISBN 978-1-86094-477-2 .
^ Перейти обратно: ^а ^б ^с Пизанти, Н.; Карвальо, А.; Марсан, Л.; Ответ, МФ (2006). «Ризотто: быстрое извлечение несовпадающих мотивов» Труды 7-го Латиноамериканского симпозиума по теоретической информатике : 757–768. CiteSeerX 10.1.1.60.1028 .
^ Перейти обратно: ^а ^б Певзнер, Пенсильвания; Сзе, С.Х. (2000). «Комбинаторные подходы к поиску тонких сигналов в последовательностях ДНК». Proc Int Conf Intell Syst Mol Biol . 8 : 269–278. ПМИД 10977088 .
^ Бейли, ТЛ; Элкан, К. (1994). «Подбор модели смеси путем максимизации ожидания для обнаружения мотивов в биополимерах». Proc Int Conf Intell Syst Mol Biol . 2 : 28–36. ПМИД 7584402 .
^ Лоуренс, CE; Альтшул, Сан-Франциско; Богуский, М.С.; Лю, Дж.С.; Нойвальд, AF; Вуттон, Дж. К. (октябрь 1993 г.). «Обнаружение тонких сигналов последовательности: стратегия выборки Гиббса для множественного выравнивания». Наука . 262 (5131): 208–214. Бибкод : 1993Sci...262..208L . дои : 10.1126/science.8211139 . ПМИД 8211139 .
^ Бейли, ТЛ; Элкан, Чарльз (январь 1995 г.). «Неконтролируемое обучение множественным мотивам в биополимерах с использованием максимизации ожидания» . Машинное обучение . 21 (1–2): 51–80. дои : 10.1007/BF00993379 .
^ Перейти обратно: ^а ^б ^с Давила, Дж.; Балла, С.; Раджасекаран, С. (2007). «Быстрые и практичные алгоритмы поиска посаженных (l, d) мотивов». IEEE/ACM Транскомпьютер Биол Биоинформ . 4 (4): 544–552. дои : 10.1109/TCBB.2007.70241 . ПМИД 17975266 . S2CID 15212174 .
^ Раджасекаран, С.; Динь, Х. (2011). «Техника ускорения алгоритмов поиска (l, d)-мотивов» . Примечания к резолюциям BMC . 4:54 . дои : 10.1186/1756-0500-4-54 . ПМК 3063805 . ПМИД 21385438 .
^ Перейти обратно: ^а ^б Динь, Х.; Раджасекаран, С.; Кундети, В.К. (2011). «PMS5: эффективный точный алгоритм решения проблемы поиска (ℓ, d)-мотивов» . БМК Биоинформатика . 12 : 410. дои : 10.1186/1471-2105-12-410 . ПМК 3269969 . ПМИД 22024209 .
^ Перейти обратно: ^а ^б Бандиопадхьяй, С.; Сахни, С.; Раджасекаран, С. (2012). «PMS6: быстрый алгоритм обнаружения мотивов». 2012 г. Вторая международная конференция IEEE по вычислительным достижениям в био и медицинских науках (ICCABS) . стр. 1–6. дои : 10.1109/ICCABS.2012.6182627 . ISBN 978-1-4673-1321-6 . ПМЦ 3744182 . ПМИД 23959399 .
^ Перейти обратно: ^а ^б ^с ^д Динь, Х.; Раджасекаран, С.; Давила, Дж. (2012). Брусич, Владимир (ред.). «qPMS7: быстрый алгоритм поиска (ℓ, d)-мотивов в последовательностях ДНК и белков» . ПЛОС ОДИН . 7 (7): е41425. Бибкод : 2012PLoSO...741425D . дои : 10.1371/journal.pone.0041425 . ПМК 3404135 . ПМИД 22848493 .
^ Давила, Дж.; Балла, С.; Раджасекаран, С. (2007). «Пампа: улучшенный алгоритм ветвей и границ для поиска посаженных (l, d) мотивов». Технический отчет . CiteSeerX 10.1.1.93.6500 .

Внешние ссылки

Раджасекаран, С.; Динь, Х. «Поиск мотивов ПМС» . Университет Коннектикута. Архивировано из оригинала 15 мая 2011 г.
Раджасекаран, С.; Динь, Х. «Поиск паноптических мотивов» . Университет Коннектикута. Архивировано из оригинала 02 августа 2011 г.

[Keich_2002-1] Перейти обратно: ^а ^б ^с Кейч, У.; Певзнер, Пенсильвания (октябрь 2002 г.). «Нахождение мотивов в сумеречной зоне» . Биоинформатика . 18 (10): 1374–1381. дои : 10.1093/биоинформатика/18.10.1374 . ПМИД 12376382 .

[Buhler_2001-2] Перейти обратно: ^а ^б Бюлер, Дж.; Томпа, М. (2002). «Нахождение мотивов с помощью случайных проекций». Дж. Компьютер. Биол . 9 (2): 225–242. CiteSeerX 10.1.1.26.2491 . дои : 10.1089/10665270252935430 . ПМИД 12015879 .

[Price_2003-3] Перейти обратно: ^а ^б ^с Прайс, А.; Рамабхадран, С.; Певзнер, Пенсильвания (октябрь 2003 г.). «Нахождение тонких мотивов путем разветвления образцов струн» . Биоинформатика . 19 (Приложение 2): ii149–55. doi : 10.1093/биоинформатика/btg1072 . ПМИД 14534184 .

[Hertz1999-4] Герц, Г.З.; Стормо, Джорджия (1999). «Идентификация структур ДНК и белков со статистически значимым выравниванием нескольких последовательностей» . Биоинформатика . 15 (7–8): 563–77. дои : 10.1093/биоинформатика/15.7.563 . ПМИД 10487864 .

[Martinez_1983-5] Мартинес, HM (июль 1983 г.). «Эффективный метод поиска повторов в молекулярных последовательностях» . Нуклеиновые кислоты Рез . 11 (13): 4629–4634. дои : 10.1093/нар/11.13.4629 . ПМК 326069 . ПМИД 6866775 .

[Brazma1998-6] Бразма, А.; Йонассен, И.; Вило, Дж.; Укконен, Э. (ноябрь 1998 г.). «Прогнозирование регуляторных элементов генов in silico в геномном масштабе» . Геном Рез . 8 (11): 1202–1215. дои : 10.1101/гр.8.11.1202 . ПМК 310790 . ПМИД 9847082 .

[Galas_1985-7] Галас, диджей; Эггерт, М.; Уотерман, М.С. (ноябрь 1985 г.). «Строгие методы распознавания образов последовательностей ДНК. Анализ промоторных последовательностей Escherichia coli». Дж. Мол. Биол . 186 (1): 117–128. дои : 10.1016/0022-2836(85)90262-1 . ПМИД 3908689 .

[Sinha_2000-8] Синха, С.; Томпа, М. (2000). «Статистический метод поиска сайтов связывания факторов транскрипции». Proc Int Conf Intell Syst Mol Biol . 8 : 344–354. ПМИД 10977095 .

[Staden_1989-9] Стаден, Р. (октябрь 1989 г.). «Методы обнаружения новых мотивов в последовательностях нуклеиновых кислот». Вычислить. Прил. Биосци . 5 (4): 293–8. дои : 10.1093/биоинформатика/5.4.293 . ПМИД 2684350 .

[Tompa_1999-10] Томпа, М. (1999). «Точный метод поиска коротких мотивов в последовательностях с применением к проблеме сайта связывания рибосом». Proc Int Conf Intell Syst Mol Biol : 262–271. ПМИД 10786309 .

[Helden_1998-11] ван Хелден, Дж.; Андре, Б.; Кольядо-Видес, Дж. (сентябрь 1998 г.). «Извлечение регуляторных сайтов из вышележащей области генов дрожжей путем компьютерного анализа частот олигонуклеотидов». Дж. Мол. Биол . 281 (5): 827–842. CiteSeerX 10.1.1.18.6830 . дои : 10.1006/jmbi.1998.1947 . ПМИД 9719638 .

[RajBallaHuang2005-12] Перейти обратно: ^а ^б ^с ^д ^и Раджасекаран, С.; Балла, С.; Хуанг, Швейцария (октябрь 2005 г.). «Точные алгоритмы решения задач с посаженными мотивами». Дж. Компьютер. Биол . 12 (8): 1117–1128. CiteSeerX 10.1.1.549.5547 . дои : 10.1089/cmb.2005.12.1117 . ПМИД 16241901 .

[Davila-13] Давила, Дж.; Раджасекаран, С. (2006). «Расширение ветвления шаблонов для обработки сложных экземпляров». Шестой симпозиум IEEE по биоинформатике и биоинженерии (BIBE'06) . стр. 65–69. дои : 10.1109/BIBE.2006.253317 . ISBN 978-0-7695-2727-7 . S2CID 17562470 . {{cite book}}: |journal= игнорируется ( помогите )

[RajBallaDavila2006-14] Давила, Дж.; Балла, С.; Раджасекаран, С. (2006). «Эффективные по пространству и времени алгоритмы поиска посаженных мотивов». Учеб. 6-я Международная конференция по вычислительной науке (ICCS 2006) / 2-й Международный семинар по исследованиям и приложениям в области биоинформатики (IWBRA 2006) LNCS 3992 : 822–829. CiteSeerX 10.1.1.94.4572 .

[Chin_2005-15] Перейти обратно: ^а ^б ^с Чин, БЮЛ ; Люнг, HCM (2005). «Алгоритмы голосования для обнаружения длинных мотивов». Материалы 3-й Азиатско-Тихоокеанской конференции по биоинформатике . стр. 261–271. CiteSeerX 10.1.1.123.2457 . дои : 10.1142/9781860947322_0026 . ISBN 978-1-86094-477-2 .

[Pisanti2006-16] Перейти обратно: ^а ^б ^с Пизанти, Н.; Карвальо, А.; Марсан, Л.; Ответ, МФ (2006). «Ризотто: быстрое извлечение несовпадающих мотивов» Труды 7-го Латиноамериканского симпозиума по теоретической информатике : 757–768. CiteSeerX 10.1.1.60.1028 .

[Pevzner_2000-17] Перейти обратно: ^а ^б Певзнер, Пенсильвания; Сзе, С.Х. (2000). «Комбинаторные подходы к поиску тонких сигналов в последовательностях ДНК». Proc Int Conf Intell Syst Mol Biol . 8 : 269–278. ПМИД 10977088 .

[Bailey_Elkan_1994-18] Бейли, ТЛ; Элкан, К. (1994). «Подбор модели смеси путем максимизации ожидания для обнаружения мотивов в биополимерах». Proc Int Conf Intell Syst Mol Biol . 2 : 28–36. ПМИД 7584402 .

[Lawrence_1993-19] Лоуренс, CE; Альтшул, Сан-Франциско; Богуский, М.С.; Лю, Дж.С.; Нойвальд, AF; Вуттон, Дж. К. (октябрь 1993 г.). «Обнаружение тонких сигналов последовательности: стратегия выборки Гиббса для множественного выравнивания». Наука . 262 (5131): 208–214. Бибкод : 1993Sci...262..208L . дои : 10.1126/science.8211139 . ПМИД 8211139 .

[Bailey_Elkan_1995-20] Бейли, ТЛ; Элкан, Чарльз (январь 1995 г.). «Неконтролируемое обучение множественным мотивам в биополимерах с использованием максимизации ожидания» . Машинное обучение . 21 (1–2): 51–80. дои : 10.1007/BF00993379 .

[Raj_Davila_Balla_2007-21] Перейти обратно: ^а ^б ^с Давила, Дж.; Балла, С.; Раджасекаран, С. (2007). «Быстрые и практичные алгоритмы поиска посаженных (l, d) мотивов». IEEE/ACM Транскомпьютер Биол Биоинформ . 4 (4): 544–552. дои : 10.1109/TCBB.2007.70241 . ПМИД 17975266 . S2CID 15212174 .

[Raj_Din_2011-22] Раджасекаран, С.; Динь, Х. (2011). «Техника ускорения алгоритмов поиска (l, d)-мотивов» . Примечания к резолюциям BMC . 4:54 . дои : 10.1186/1756-0500-4-54 . ПМК 3063805 . ПМИД 21385438 .

[Raj_Din_Kundeti_2012-23] Перейти обратно: ^а ^б Динь, Х.; Раджасекаран, С.; Кундети, В.К. (2011). «PMS5: эффективный точный алгоритм решения проблемы поиска (ℓ, d)-мотивов» . БМК Биоинформатика . 12 : 410. дои : 10.1186/1471-2105-12-410 . ПМК 3269969 . ПМИД 22024209 .

[Bandyo_Sahni_Raj_2012-24] Перейти обратно: ^а ^б Бандиопадхьяй, С.; Сахни, С.; Раджасекаран, С. (2012). «PMS6: быстрый алгоритм обнаружения мотивов». 2012 г. Вторая международная конференция IEEE по вычислительным достижениям в био и медицинских науках (ICCABS) . стр. 1–6. дои : 10.1109/ICCABS.2012.6182627 . ISBN 978-1-4673-1321-6 . ПМЦ 3744182 . ПМИД 23959399 .

[Raj_Hieu_2012-25] Перейти обратно: ^а ^б ^с ^д Динь, Х.; Раджасекаран, С.; Давила, Дж. (2012). Брусич, Владимир (ред.). «qPMS7: быстрый алгоритм поиска (ℓ, d)-мотивов в последовательностях ДНК и белков» . ПЛОС ОДИН . 7 (7): е41425. Бибкод : 2012PLoSO...741425D . дои : 10.1371/journal.pone.0041425 . ПМК 3404135 . ПМИД 22848493 .

[Davila_Balla_Raj_techrpt-26] Давила, Дж.; Балла, С.; Раджасекаран, С. (2007). «Пампа: улучшенный алгоритм ветвей и границ для поиска посаженных (l, d) мотивов». Технический отчет . CiteSeerX 10.1.1.93.6500 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]