Изменения
→Использование графов де Брюина
'''Время работы''': <tex> O(n^{l+1} \cdot substring) = O(|E| \cdot l) </tex>
== Использование Применение графов де Брюина ==
{{Задача
3. Отсюда следует, что в последовательности содержится <tex> n^l </tex> различных подстрок длины <tex> l </tex>. И короче последовательность получить нельзя. Значит, мы получили ответ за <tex> O((|E| \cdot (l-1)) + (|E| + |V|)) = O(|E| \cdot (l-1)) </tex>, то есть за время построения графа де Брюина <tex> (n, l-1) </tex>.
{{Задача
|definition =
Даны неповторяющиеся последовательности ''нуклеотидов'' (''риды'') длины <tex> l </tex>. Известно, что все подстроки генома длины <tex> l </tex> входят в данное множество ридов. Построить возможный геном.
}}
'''Пояснение''':
Геном (как и его части <tex> - </tex> риды) является словом из 4-символьного алфавита <tex> \{A, G, C, T\} </tex>, где символы так же называются нуклеотидами. В реальности длины ридов находятся обычно в диапазоне 100-1000 нуклеотидов, а геном может содержать от <tex> 10^6 </tex> нуклеотидов у простейших организмов. При этом учёные могут получать информацию только о ридах (в силу размера последовательностей) физическим путем (''метод секвенирования'').
'''Решение''':
Решение этой задачи очень простое после решения предыдущей задачи. Построим граф G, где вершинами будут являться суффиксы и префиксы длины <tex> l - 1 </tex> всех ридов. Получили подграф графа де Брюина <tex> (4, l-1) </tex> (подграф, так как в нём есть не обязательно все <tex> 4^{l - 1} </tex> вершины), где каждому ребру соответствует рид. Найдём в нём эйлеров цикл. Он существует, так как на геном было наложено условие о том, что все его подстроки длины <tex> l </tex> входят в наше множество ридов. Этот цикл является возможным ответом. Очевидно, что единственно верный ответ (коим является реальный геном реального существа) получить мы не сможем, потому что эйлеров цикл может быть не единственным, и цикл можно сдвигать.
'''Комментарий''':
К сожалению, в реальности есть очень много проблем (кроме того, что алгоритм работает за <tex> O(4^l \cdot l) </tex>). Во-первых, как можно догадаться из пояснения: едва ли риды обязательно будут неповторяющимися. Во-вторых, данные о ридах тоже получаются с некоторой вероятностью (как правило, ошибка в нуклеотиде имеет вероятность около 0.001, но вблизи "края" генома может достигать и 0.3). В-третьих, риды не могут иметь фиксированную длину. Таким образом, задача решается за экспоненциальное время, и с довольно жёсткими условиями на входные данные. Однако многие реальные ''ассемблеры'', собирающие геномы (или их части, заметно превышающие размер рида), действительно используют идеи графа де Брюина, но более усложнённые.
