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

материалы................................................................................................ 72
Оценка «О большого» (Big-O)........................................................................................ 72
Вероятности паттернов в строке.................................................................................. 73
Самый красивый эксперимент в биологии.................................................................. 78
Направленность цепей ДНК.......................................................................................... 80
Ханойские башни........................................................................................................... 81
Парадокс перекрывающихся слов................................................................................ 83
Библиографические примечания....................................................................................... 85

Глава 2. Какие сегменты ДНК играют роль
молекулярных часов? .................................................................................... 87
Есть ли у нас «часовой ген»?............................................................................................... 88
Найти мотив сложнее, чем вы думаете.............................................................................. 89
Идентификация вечернего элемента........................................................................... 89
Игра в прятки с мотивами............................................................................................. 90
Метод грубой силы поиска мотива............................................................................... 92
Считаем мотивы.................................................................................................................. 93
От мотивов к матрицам профиля и консенсусным строкам...................................... 93
На пути к более адекватной функции оценки мотивов.............................................. 96
Энтропия и motif logo.................................................................................................... 97
От поиска мотива к поиску медианной строки................................................................. 98
Задача поиска мотива.................................................................................................... 98
Переформулировка задачи поиска мотива.................................................................. 99
Задача поиска медианной строки...............................................................................101
Почему мы переформулировали задачу поиска мотива?..........................................103
Жадный алгоритм поиска мотива.....................................................................................104
Использование матрицы профиля для бросания костей...........................................104
Анализ жадного алгоритма поиска мотива................................................................106
Поиск мотива и Оливер Кромвель.....................................................................................107
Какова вероятность того, что завтра не взойдет солнце?..........................................107
Правило преемственности Лапласа.............................................................................108
Улучшенный алгоритм жадного поиска мотивов......................................................109
Рандомизированный поиск мотива..................................................................................112
Игра в кости для поиска мотивов................................................................................112
Почему рандомизированный поиск мотивов работает.............................................114
Почему рандомизированный алгоритм работает так хорошо?......................................116
Сэмплирование по Гиббсу.................................................................................................119
Сэмплирование по Гиббсу в действии..............................................................................121
Эпилог. Как туберкулез впадает в спячку, чтобы спрятаться от антибиотиков?...........124
Зарядная станция...............................................................................................................127
Решение задачи медианной строки............................................................................127
Сопутствующие материалы...............................................................................................128
Экспрессия генов..........................................................................................................128
ДНК-чипы......................................................................................................................128
Игла Бюффона...............................................................................................................129

Содержание

7

Сложности в поиске мотива.........................................................................................132
Относительная энтропия.............................................................................................132
Библиографические примечания......................................................................................134

Глава 3. Как мы собираем геномы?..................................................135
Взрывающиеся газеты........................................................................................................136
Задача реконструкции строки...........................................................................................139
Сборка генома сложнее, чем вы думаете....................................................................139
Реконструкция строк из k-меров.................................................................................139
Повторы усложняют сборку генома.............................................................................142
Реконструкция строк как прогулка по графу перекрытий..............................................143
От строки к графу..........................................................................................................143
Геном --">