Павел Певзнер , Филлип Компо - Алгоритмы биоинформатики

исчезает..............................................................................................................146
Два способа представления графов.............................................................................147
Гамильтоновы пути и универсальные строки............................................................148
Другой граф для реконструкции строк.............................................................................150
Склеивание узлов и графы де Брюйна........................................................................150
Прогулка по графу де Брюйна............................................................................................152
Эйлеровы пути..............................................................................................................152
Другой способ построения графов де Брюйна............................................................153
Построение графов де Брюйна из композиции k-меров...........................................155
Графы де Брюйна в сравнении с графами перекрытия.............................................156
Семь мостов Кенигсберга...................................................................................................157
Теорема Эйлера...................................................................................................................160
От теоремы Эйлера к алгоритму нахождения эйлеровых циклов..................................163
Построение эйлеровых циклов....................................................................................163
От эйлеровых циклов к эйлеровым путям..................................................................164
Создание универсальных строк...................................................................................165
Сборка геномов из рид-пар...............................................................................................167
От ридов к рид-парам...................................................................................................167
Преобразование рид-пар в длинные виртуальные риды..........................................169
От композиции к спаренной композиции..................................................................170
Парные графы графы де Брюйна.................................................................................172
Ловушка парных графов де Брюйна............................................................................173
Эпилог. Сборка генома – работа с реальными данными секвенирования.....................176
Разбиваем риды на k-меры..........................................................................................176
Фрагментация генома на контиги...............................................................................177
Сборка ридов с возможными ошибками....................................................................179
Определение кратности ребер в графах де Брюйна...................................................180
Зарядные станции..............................................................................................................181
Влияние склейки на матрицу смежности...................................................................181
Генерация всех эйлеровых циклов..............................................................................182
Реконструкция строки, записанной как путь в парном графе де Брюйна................184
Максимальные неветвящиеся пути в графе...............................................................186
Сопутствующие материалы...............................................................................................187
Краткая история технологий секвенирования ДНК...................................................187
Повторы в геноме человека.........................................................................................189
Графы.............................................................................................................................190
Игра «Икосиан».............................................................................................................193
Разрешимые и неразрешимые задачи........................................................................194

8

Содержание

От Эйлера до Гамильтона и де Брюйна.......................................................................195
Семь мостов Калининграда..........................................................................................196
Подводные камни сборки двухцепочечной ДНК........................................................197
«ЛУЧШАЯ» теорема.......................................................................................................198
Библиографические примечания......................................................................................199

Глава 4. Как мы секвенируем антибиотики?...........................201
Открытие антибиотиков....................................................................................................202
Как бактерии производят антибиотики?..........................................................................203
Как пептиды кодируются геномом..............................................................................203
Где в геноме Bacillus brevis закодирован тироцидин?...............................................206
От линейных к циклическим пептидам......................................................................207
Уклоняясь от центральной догмы молекулярной биологии...........................................208
Секвенирование антибиотиков путем их дробления на части.......................................209
Введение в масс-спектрометрию.................................................................................209
Задача секвенирования циклопептидов.....................................................................210
Алгоритм грубой силы для секвенирования циклопептидов.........................................212
Алгоритм ветвей и границ для секвенирования --">