Изменения
→Применение графов де Брюина
1. Составим граф де Брюина <tex> (n, l-1) </tex>.
2. Найдём в построенном графе эйлеров цикл. Он существует, так как граф де Брюина эйлеров (смпо лемме 1. свойства)
3. Слово, соответствующее первой вершине цикла, возьмём полностью (<tex> l - 1 </tex> символов), затем будем последовательно добавлять в конец строки последний символ слова вершины, в которую был осуществлён переход. Так как рёбер <tex> n^l </tex>, получим последовательность длиной <tex> n^l + l - 1 </tex>.
'''Комментарий''':
К сожалению, в реальности есть очень много проблем (кроме того, что алгоритм работает за <tex> O(4^l \cdot l) </tex>), в реальности есть немало технических проблем: 1. Во-первых, как Как можно догадаться из пояснения: едва ли риды обязательно будут неповторяющимися. Во-вторых, данные 2. Данные о ридах тоже получаются могут быть получены лишь с некоторой вероятностью (как правило, ошибка в нуклеотиде имеет вероятность около <tex> 0.001 </tex>, но вблизи "края" генома она может достигать и <tex> 0.3 </tex>). В-третьих, риды 3. Риды не могут иметь фиксированную длинув силу особенностей метода секвенирования. Таким образом '''Вывод''': Несмотря на то, что задача не решается за экспоненциальное времяв общем случае приведённым алгоритмом, и с довольно жёсткими условиями на входные данные. Однако многие реальные граф де Брюина действительно используется в ''ассемблерыассемблерах''(программах, собирающие геномы (собирающих геном или их его большие части, заметно превышающие размер ридаиз ридов), действительно используют идеи графа де Брюина, но более усложнённыес заметными усложнениями.
== См. также ==
