В области вычислительной биологии , А посажен поиск мотива (ПМС) , также известный как ( L, D ) -motif поиска (LDMS) представляет собой способ для идентификации консервативных мотивов в пределах набора нуклеиновых кислот или последовательности пептидов .
Известно, что ПМС является NP-полным . В время Сложность большинства посаженных алгоритмов поиска мотива экспоненциально зависит от размера алфавита и л . Проблема ПМС была впервые представлена Кейчем и Певзнером. [1]
Проблема идентификации значимых паттернов (например, мотивов) на основе биологических данных широко изучалась, поскольку они играют жизненно важную роль в понимании функции генов , болезней человека и могут служить мишенями для терапевтических препаратов .
Описание
Задачу поиска можно резюмировать следующим образом:
Входные данные - n строк (s 1 , s 2 ,…, 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 1 , s 2 , s 3 ,…, s n } - заданный набор входных строк из алфавита Σ. Л -mer любой строки не что иное, как подстрока строки длины л . Пусть d H (a, b) обозначает расстояние Хэмминга между любыми двумя l- мерами a и b . Пусть a - l -мер, а s - входная строка. Тогда, пусть d H (a, s) стоят на расстояние Хемминга между минимальной и любого л -mer б о с . Если a - любой l -мер, а S - набор входных строк, тогда пусть d H (a, S) обозначает max sєS d H (a, s) . Пусть u - любой l -мер. Тогда d -окрестность u (обозначаемая как B d (u) ) есть не что иное, как множество всех l -меров v таких, что d H (u, v) ≤ d . Другими словами, B d (u) = {v: d H (u, v) ≤d} . Обратитесь к любому такому л -mer V в качестве г -neighbor из ц . B d (x, y) используется для обозначения общей d- окрестности x и y , где x и y - два l- мера. B d (x, y) - это не что иное, как набор всех l -меров, находящихся на расстоянии d как от x, так и от y . Аналогичным образом можно определить B d (x, y, z) и т. Д.
Алгоритмы
В научной литературе описаны многочисленные алгоритмы решения проблемы ПМС. Эти алгоритмы можно разделить на два основных типа. Те алгоритмы, которые могут не возвращать оптимальный ответ (ы), называются алгоритмами приближения (или эвристическими алгоритмами), а те, которые всегда возвращают оптимальный ответ (ы), называются точными алгоритмами.
Приблизительно
Примеры приближенных (или эвристических) алгоритмов включают случайную проекцию , [2] PatternBranching, [3] MULTIPROFILER, [1] CONSENSUS, [4] и ProfileBranching. [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 ) с помощью l -меров в ведре.
Ветвление по образцу
Этот алгоритм [3] является алгоритмом локального поиска . Если u - любой l -мер, то существуют l -меры, являющиеся d -соседями u для цепочек ДНК. Этот алгоритм начинается с каждого l -мера u во входных данных, ищет соседей u , оценивает их соответствующим образом и выводит соседа с наилучшей оценкой.
Точный
Известно много точных алгоритмов решения проблемы PMS. Примеры включают в себя (Martinez 1983), [5] (Brazma, et al. 1998), [6] (Galas, et al. 1985), [7] (Sinha, et al. 2000), [8] ( Staden 1989), [9] (Tompa 1999), [10] (Helden, et al. 1998) [11] (Rajasekaran, et al.), [12] (Davila and Rajasekaran 2006), [13] (Davila, Balla, and Rajasekaran 2006), [14] Голосование [15] и RISOTTO. [16]
ПОБЕДИТЕЛЬ и SP-STAR
Алгоритм WINNOWER [17] является эвристическим алгоритмом и работает следующим образом. Если A и B - два экземпляра одного и того же мотива в двух разных входных строках, то расстояние Хэмминга между A и B не превышает 2 d . Можно показать, что ожидаемое расстояние Хэмминга между A и B равно. WINNOWER создает на входе коллекцию C всех возможных l -меров. Строится граф G (V, E), в котором каждый l- мер графа C будет узлом. Два узла u и v в G соединены ребром тогда и только тогда, когда расстояние Хэмминга между u и v не превышает 2 d, и они происходят из двух разных входных строк.
Если М является ( л , д ) мотив , и , если M 1 , M 2 , ..., и М п являются экземплярами М во входных строк, то, очевидно, эти случаи будут образовывать верхушку в G . Алгоритм WINNOWER состоит из двух этапов. На первом этапе, он идентифицирует большие клики в G . На втором этапе каждая такая клика исследуется, чтобы увидеть, можно ли выделить из этой клики мотив. Поскольку проблема CLIQUE неразрешима , WINNOWER использует эвристику для решения CLIQUE. Он итеративно создает клики все большего и большего размера. Если N = mn , то время работы алгоритма равноНа практике этот алгоритм работает в разумные сроки, особенно при малых значениях d . Другой алгоритм, называемый SP-STAR, [17] быстрее, чем WINNOWER, и использует меньше памяти. Алгоритм WINNOWER обрабатывает все ребра G одинаково, не различая ребра на основе сходства. SP-STAR правильно оценивает l -меры C, а также ребра G и, следовательно, удаляет больше ребер, чем WINNOWER за итерацию.
(Bailey and Elkan, 1994) [18] использует алгоритмы максимизации математического ожидания, в то время как выборка Гиббса используется (Lawrence et al., 1993). [19] MULTIPROFILER [1] MEME, [20] также являются известными алгоритмами PMS.
Серия PMS
За последнее десятилетие в лаборатории Раджасекарана была разработана серия алгоритмов с префиксом PMS . Некоторые из этих алгоритмов описаны ниже.
PMS0
PMSo [12] работает следующим образом. Пусть s 1 , s 2 ,…, s n - заданный набор входных строк, каждая длиной m . Пусть C - набор l -меров в s 1 . Пусть C '= ∪ u∈C B d ( u ). Для каждого элемента v из C ' проверьте, является ли он допустимым ( l , d ) -мотивом или нет. Учитывая l -mer v , проверка того, является ли он действительным ( l , d ) -мотивом, может быть произведена за время O ( mnl ). Таким образом, время работы PMS0, предполагая размер алфавита 4, равно.
PMS1
Этот алгоритм [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 (используя сортировку по основанию) и удалите все дубликаты.
- Вычислить:. Это можно сделать, объединив списки L 1 , L 2 ,…, L n . Все l -меры в этом пересечении являются действительными мотивами ( l , d ).
PMS2
Пусть интересующий мотив M имеет длину l . Если М происходит в каждой входной строке , то любая подстрока из M также происходит в каждой входной строке. Здесь возникновение означает появление в пределах расстояния Хэмминга d . Отсюда следует, что существует не менее l - k +1 строк каждая длиной k (для k ≤ l ), такая что каждая из них встречается в каждой входной строке.
Пусть Q некоторая совокупность K -mers в M . Обратите внимание, что в каждой входной строке s i будет по крайней мере одна позиция i j, такая, что k- мер Q встречается, начиная с i j . Другой k -мер Q встречается, начиная с i j +1 и так далее, причем последний k -мер встречается в i j + l - k . Л -mer может быть получен путем сочетания этого K -mers , которые происходят , начиная с каждым таким я J .
PMS2 [12] работает следующим образом. На первом этапе найдите все мотивы ( k , d ), присутствующие во всех входных строках (для некоторого подходящего значения k < l ). На втором этапе ищите ( l - k +1) из этих ( k , d ) мотивов, которые появляются, начиная с последовательных позиций в каждой из входных строк. Из каждого такого набора ( l - k +1) ( k , d ) -мотивов может быть сгенерирован l -мер (если это возможно). Каждый такой l -мер является кандидатом ( l , d ) -мотивом. Для каждого мотива-кандидата проверьте, является ли он ( l , d ) -мотивом или нет, за время O ( mnl ). Этот l -mer возвращается как результат, если это ( l , d ) -мотив.
PMS3
Этот алгоритм [12] позволяет обрабатывать большие значения d . Пусть d '= d / 2. Пусть M - мотив, который нужно найти с помощью | M | = l = 2 l 'для некоторого целого l '. Пусть M 1 относится к первой половине M, а M 2 - к следующей половине. Пусть s = a 1 a 2 … a m будет одной из входных строк. M встречается в каждой входной строке. Пусть вхождение M (на расстоянии Хэмминга d ) в s начинается с позиции i . Пусть s '= a i a i + 1 … a i + l'-1 и s ' '= a i + l '… a i + l-1 . Ясно, что либо расстояние Хэмминга между M 1 и s 'не больше d ', либо расстояние Хэмминга между M 2 и s '' не больше d '. Либо M 1, либо M 2 встречается в каждой входной строке на расстоянии Хэмминга не более d '. В результате, по крайней мере, в n 'строках (где n ' = n / 2) встречается либо M 1, либо M 2 с расстоянием Хэмминга не более d . Алгоритм сначала получает все ( l ', d ') -мотивы, которые встречаются по крайней мере в n / 2 входных строк. Затем он использует эти мотивы и вышеприведенные наблюдения для идентификации всех ( l , d ) -мотивов, присутствующих во входных строках.
PMSPrune
Этот алгоритм вводит древовидную структуру для кандидатов в мотив и использует алгоритм ветвей и границ для уменьшения пространства поиска. [21] Пусть S = { s 1 , s 2 ,…, s n } будет заданным набором входных строк. PMSprune следует той же стратегии, что и PMS0: для каждого l- числа y в s 1 он генерирует набор соседей 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 1 , то время работы PMSPrune будет не меньше времени работы PMS0. PMSPrune использует некоторые условия отсечения для отсечения поддеревьев, в которых не может быть никаких мотивов.
- Для l- мер x , который соответствует узлу в поддереве высотой h , алгоритм использует значение d H (x, S) и h для отсечения потомков x .
- PMSPrune вычисляет значение d H (x, S) для узлов ( x ) в дереве поэтапно, принимая во внимание способ создания окрестности.
PMS4
PMS4 [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 -мера v в C сделать
- Проверьте, является ли v допустимым мотивом за время O ( mnl ). Если да, выведите v .
PMS5 и PMS6
PMS5 [23] является расширением PMS0. Если S = { s 1 , s 2 ,…, s n } - это набор строк (не обязательно одинаковой длины), пустьОбозначим ( л , д ) -motifs присутствует в S . Пусть S '= { s 2 , s 3 ,…, s n }. PMS5 вычисляет ( l , d ) -мотивы 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 находится в. При посещении любого узла t проверьте, существует ли потомок t ' от t, такой что t' находится в. Удалите поддерево с корнем в t, если такого потомка нет. В PMS5 проблема проверки, есть ли у t потомок, который находится вформулируется как целочисленная линейная программа (ЦЛП) от десяти переменных. Эта ILP решается за O (1) раз. Решение экземпляров ILP выполняется как этап предварительной обработки, а результаты сохраняются в таблице поиска.
Алгоритм PMS6 [24] является расширением PMS5, улучшающим этап предварительной обработки, а также использующим эффективные методы хеширования для хранения таблиц поиска. В результате он обычно быстрее, чем PMS5.
Шибдас Бандйопадхьяй, Сартадж Сахни, Сангутевар Раджасекаран, «PMS6: быстрый алгоритм для обнаружения мотивов», iccabs, стр. 1–6, 2012 2-я Международная конференция IEEE по вычислительным достижениям в биологических и медицинских науках, 2012 г.
qPMSPrune и qPMS7
Для набора S = { s 1 , s 2 ,…, 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 - один из первых алгоритмов для решения этой версии проблемы PMS. [21] qPMSPrune использует следующий факт: если M - любой ( l, d, q ) -мотив входных строк s 1 , s 2 ,…, s n , то существует i (с 1 ≤ i ≤ n - q + 1) и l -мертакое, что 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 1 , s 2 ,…, s n , то существует 1 ≤ i ≠ j ≤ n и l -мери l -мертакое, что M находится ви 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 , алгоритм идентифицирует все элементыкоторые являются ( l, d, q -2) мотивами (по отношению к входным строкам, отличным от s i и s j ). Ациклический граф используется для представления и исследовать. Назовем этот граф G d (x, y) . G d (x, y) проходит сначала в глубину. Как и в qPMSPrune, qPMS7 также использует некоторые условия сокращения для сокращения подграфов G d (x, y) .
РИЗОТТО
RISOTTO [16] использует суффиксное дерево для идентификации ( l, d ) -мотивов. Он чем-то похож на PMS0. Для каждого l -мера в s 1 он генерирует 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] Pampa, [26] Голосование, [15] RISOTTO, [16] PMS5, [23] PMS6, [24] qPMS7. [25]
В следующей таблице алфавит ∑ = { A , C , G , T }, n = 20, m = 600 и q = n = 20.
Алгоритм | (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 кв.м. | - | - | - | - |
Рекомендации
- ^ a b c Keich, U .; Певзнер, П.А. (октябрь 2002 г.). «Нахождение мотивов в сумеречной зоне» . Биоинформатика . 18 (10): 1374–1381. DOI : 10.1093 / биоинформатики / 18.10.1374 . PMID 12376382 .
- ^ а б Buhler, J .; Томпа, М. (2002). «Поиск мотивов по случайным проекциям». J. Comput. Биол . 9 (2): 225–242. CiteSeerX 10.1.1.26.2491 . DOI : 10.1089 / 10665270252935430 . PMID 12015879 .
- ^ а б в Цена, А .; Ramabhadran, S .; Певзнер, П.А. (октябрь 2003 г.). «Обнаружение тонких мотивов путем разветвления от сэмплов струн» . Биоинформатика . 19 Дополнение 2: ii149–55. DOI : 10.1093 / биоинформатики / btg1072 . PMID 14534184 .
- ^ Герц, ГЗ; Стормо, GD (1999). «Идентификация образцов ДНК и белков со статистически значимым выравниванием нескольких последовательностей» . Биоинформатика . 15 (7–8): 563–77. DOI : 10.1093 / биоинформатики / 15.7.563 . PMID 10487864 .
- ^ Мартинес, HM (июль 1983 г.). «Эффективный метод поиска повторов в молекулярных последовательностях» . Nucleic Acids Res . 11 (13): 4629–4634. DOI : 10.1093 / NAR / 11.13.4629 . PMC 326069 . PMID 6866775 .
- ^ Brazma, A .; Jonassen, I .; Vilo, J .; Укконен, Э. (ноябрь 1998 г.). «Прогнозирование регуляторных элементов генов in silico в геномном масштабе» . Genome Res . 8 (11): 1202–1215. DOI : 10.1101 / gr.8.11.1202 . PMC 310790 . PMID 9847082 .
- ^ Гала, DJ; Eggert, M .; Waterman, MS (ноябрь 1985 г.). «Строгие методы распознавания образов для последовательностей ДНК. Анализ промоторных последовательностей из Escherichia coli». J. Mol. Биол . 186 (1): 117–128. DOI : 10.1016 / 0022-2836 (85) 90262-1 . PMID 3908689 .
- ^ Sinha, S .; Томпа, М. (2000). «Статистический метод поиска сайтов связывания факторов транскрипции». Proc Int Conf Intell Syst Mol Biol . 8 : 344–354. PMID 10977095 .
- ^ Staden, R. (октябрь 1989 г.). «Методы обнаружения новых мотивов в последовательностях нуклеиновых кислот». Comput. Прил. Biosci . 5 (4): 293–8. DOI : 10.1093 / биоинформатики / 5.4.293 . PMID 2684350 .
- ^ Томпа, М. (1999). «Точный метод поиска коротких мотивов в последовательностях с приложением к проблеме сайта связывания рибосом». Proc Int Conf Intell Syst Mol Biol : 262–271. PMID 10786309 .
- ^ van Helden, J .; Андре, Б.; Колладо-Видес, Дж. (Сентябрь 1998 г.). «Извлечение регуляторных участков из вышележащей области генов дрожжей с помощью компьютерного анализа частот олигонуклеотидов». J. Mol. Биол . 281 (5): 827–842. CiteSeerX 10.1.1.18.6830 . DOI : 10.1006 / jmbi.1998.1947 . PMID 9719638 .
- ^ а б в г д Rajasekaran, S .; Balla, S .; Хуанг, Швейцария (октябрь 2005 г.). «Точные алгоритмы решения задач с посадочными мотивами». J. Comput. Биол . 12 (8): 1117–1128. CiteSeerX 10.1.1.549.5547 . DOI : 10,1089 / cmb.2005.12.1117 . PMID 16241901 .
- ^ Davila, J .; Раджашекаран, С. (2006). Расширение ветвления по шаблону для обработки сложных экземпляров . Биоинформатика и биоинжиниринг . С. 65–69. DOI : 10.1109 / BIBE.2006.253317 . ISBN 978-0-7695-2727-7. S2CID 17562470 .
- ^ Davila, J .; Balla, S .; Раджашекаран, S (2006). "Пространственно-временные алгоритмы поиска мотивов растений". Proc. 6-я Международная конференция по вычислительной науке (ICCS 2006) / 2-й Международный семинар по биоинформатическим исследованиям и приложениям (IWBRA 2006) LNCS 3992 : 822–829. CiteSeerX 10.1.1.94.4572 .
- ^ а б в Подбородок, FYL ; Леунг, HCM (2005). Алгоритмы голосования для выявления длинных мотивов . Труды Третьей Азиатско-Тихоокеанской конференции по биоинформатике (APBC) . С. 261–271. CiteSeerX 10.1.1.123.2457 . DOI : 10.1142 / 9781860947322_0026 . ISBN 978-1-86094-477-2.
- ^ а б в Pisanti, N .; Carvalho, A .; Marsan, L .; Сагот, М.Ф. (2006). «Ризотто: быстрое извлечение несовпадающих мотивов». Труды 7-го латиноамериканского симпозиума по теоретической информатике : 757–768. CiteSeerX 10.1.1.60.1028 .
- ^ а б Певзнер, П.А. Зе, SH (2000). «Комбинаторные подходы к обнаружению тонких сигналов в последовательностях ДНК». Proc Int Conf Intell Syst Mol Biol . 8 : 269–278. PMID 10977088 .
- ^ Бейли, TL; Элкан, К. (1994). «Подбор модели смеси путем максимизации ожиданий для обнаружения мотивов в биополимерах». Proc Int Conf Intell Syst Mol Biol . 2 : 28–36. PMID 7584402 .
- ^ Лоуренс, CE; Альтшул, СФ; Богуски, М.С.; Лю, Дж. С.; Neuwald, AF; Вуттон, JC (октябрь 1993 г.). «Обнаружение тонких сигналов последовательности: стратегия выборки Гиббса для множественного выравнивания». Наука . 262 (5131): 208–214. Bibcode : 1993Sci ... 262..208L . DOI : 10.1126 / science.8211139 . PMID 8211139 .
- ^ Бейли, TL; Элкан, Чарльз (январь 1995 г.). «Неконтролируемое обучение множеству мотивов в биополимерах с использованием максимизации ожидания» . Машинное обучение . 21 (1-2): 51–80. DOI : 10.1007 / BF00993379 .
- ^ а б в Davila, J .; Balla, S .; Раджасекаран, С. (2007). «Быстрые и практичные алгоритмы поиска растительных (л, г) мотивов». IEEE / ACM Trans Comput Biol Bioinform . 4 (4): 544–552. DOI : 10.1109 / TCBB.2007.70241 . PMID 17975266 . S2CID 15212174 .
- ^ Rajasekaran, S .; Динь, Х. (2011). «Ускорение алгоритмов поиска (l, d) -мотивов» . BMC Res Notes . 4 : 54. DOI : 10,1186 / 1756-0500-4-54 . PMC 3063805 . PMID 21385438 .
- ^ а б Dinh, H .; Rajasekaran, S .; Кундети, ВК (2011). «PMS5: эффективный точный алгоритм для задачи поиска (ℓ, d) -мотива» . BMC Bioinformatics . 12 : 410. DOI : 10,1186 / 1471-2105-12-410 . PMC 3269969 . PMID 22024209 .
- ^ а б Bandyopadhyay, S .; Sahni, S .; Раджасекаран, С. (2012). PMS6: быстрый алгоритм обнаружения мотивов . 2-я Международная конференция IEEE по вычислительным достижениям в биологических и медицинских науках . С. 1–6. DOI : 10.1109 / ICCABS.2012.6182627 . ISBN 978-1-4673-1321-6. PMC 3744182 . PMID 23959399 .
- ^ а б в г Dinh, H .; Rajasekaran, S .; Давила, Дж. (2012). Брусич, Владимир (ред.). «qPMS7: быстрый алгоритм для поиска (ℓ, d) -мотивов в ДНК и белковых последовательностях» . PLOS ONE . 7 (7): e41425. Bibcode : 2012PLoSO ... 741425D . DOI : 10.1371 / journal.pone.0041425 . PMC 3404135 . PMID 22848493 .
- ^ Davila, J .; Balla, S .; Раджасекаран, С. (2007). «Пампа: улучшенный алгоритм ветвей и границ для поиска мотивов растений (l, d)». Технический отчет . CiteSeerX 10.1.1.93.6500 .
Внешние ссылки
- Rajasekaran, S .; Динь, Х. «Поиск мотива PMS» . Университет Коннектикута. Архивировано из оригинала на 2011-05-15.
- Rajasekaran, S .; Динь, Х. "Паноптический поиск мотивов" . Университет Коннектикута. Архивировано из оригинала на 2011-08-02.