Алгоритмы биоинформатики
Покупка
Тематика:
Общая биология
Издательство:
ДМК Пресс
Перевод:
Люско И. Л.
Год издания: 2023
Кол-во страниц: 684
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
ВО - Специалитет
ISBN: 978-5-93700-175-7
Артикул: 817236.01.99
Перед вами одно из самых популярных за рубежом руководств по биоинформатике. Книга обеспечивает уникальный баланс между практическими задачами современной биологии и фундаментальными алгоритмическими идеями. Каждая глава начинается с биологического вопроса, а затем неуклонно развивается алгоритмическая сложность, необходимая для ответа на него. Сотни упражнений включены непосредственно в текст и помогают разобраться в непростом материале.
Издание предназначено специалистам в области анализа данных, а также будет полезно ученым, инженерам, студентам и аспирантам, работающим на стыке биологии и информатики.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Филлип Компо и Павел Певзнер Алгоритмы биоинформатики
Bioinformatics Algorithms An Active Learning Approach PHILLIP COMPEAU AND PAVEL PEVZNER
Москва, 2023 Алгоритмы биоинформатики ФИЛЛИП КОМПО И ПАВЕЛ ПЕВЗНЕР
УДК 575.112 ББК 28.071.3 К63 Певзнер П., Компо Ф. К63 Алгоритмы биоинформатики / пер. с англ. И. Л. Люско. – М.: ДМК Пресс, ISBN 978-5-93700-175-7 Перед вами одно из самых популярных за рубежом руководств по биоинформатике. Книга обеспечивает уникальный баланс между практическими задачами современной биологии и фундаментальными алгоритмическими идеями. Каждая глава начинается с биологического вопроса, а затем неуклонно развивается алгоритмическая сложность, необходимая для ответа на него. Сотни упражнений включены непосредственно в текст и помогают разобраться в непростом материале. Издание предназначено специалистам в области анализа данных, а также будет полезно ученым, инженерам, студентам и аспирантам, работающим на стыке биологии и информатики. УДК 575.112 ББК 28.071.3 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Copyright © 2015 by Phillip Compeau and Pavel Pevzner ISBN 978-5-93700-175-7 (рус.) © Перевод, оформление, издание, ДМК Пресс, 2022
Содержание От издательства....................................................................................................... 16 Глава 1. В каком месте генома начинается репликация ДНК?............................................................................................... 17 Путешествие в тысячу миль…............................................................................................ 18 Скрытые сообщения в точке начала репликации............................................................. 20 DnaA-боксы.................................................................................................................... 20 Скрытые сообщения в «Золотом жуке»........................................................................ 21 Подсчет слов................................................................................................................... 22 Задача поиска часто встречающихся слов................................................................... 23 Более быстрый подход к задаче частых слов............................................................... 24 Часто используемые слова в Vibrio cholerae................................................................ 26 Некоторые скрытые сообщения более примечательны, чем другие............................... 27 Взрыв скрытых сообщений................................................................................................ 31 Поиск скрытых сообщений в нескольких геномах..................................................... 31 Задача поиска сгустков................................................................................................. 32 Самое простое объяснение процесса репликации ДНК................................................... 34 Асимметрия репликации.................................................................................................... 37 Специфическая статистика прямой и обратной полуцепей............................................ 41 Неизвестный биологический феномен или статистическая случайность?.............. 41 Дезаминирование.......................................................................................................... 43 Диаграмма смещения.................................................................................................... 44 Некоторые скрытые сообщения более неуловимы, чем другие...................................... 47 Последняя попытка найти DnaA-боксы в E. Coli............................................................... 51 Эпилог. Осложнения в предсказаниях ori.......................................................................... 53 Открытые проблемы........................................................................................................... 55 Множественные точки начала репликации в бактериальном геноме...................... 55 Поиск источников репликации у архей....................................................................... 57 Поиск точек начала репликации у дрожжей................................................................ 59 Вычисление вероятностей паттернов в строке........................................................... 60 Зарядные станции............................................................................................................... 61 Массив частот................................................................................................................. 61 Преобразование Patterns в Numbers и наоборот......................................................... 63 Поиск часто встречающихся слов путем сортировки................................................. 65
6 Содержание Решение задачи поиска сгустков.................................................................................. 66 Решение задачи часто встречающихся слов с несовпадениями................................ 68 Генерация окрестности строки..................................................................................... 69 Поиск часто встречающихся слов с несовпадениями путем сортировки................. 71 Сопутствующие материалы................................................................................................ 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 Геном исчезает..............................................................................................................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 Алгоритм ветвей и границ для секвенирования циклопептидов..................................214 Масс-спектрометрия и гольф............................................................................................217 От теоретических к реальным спектрам....................................................................217 Адаптация секвенирования циклопептидов для спектров с ошибками..................218 От 20 до более чем 100 аминокислот................................................................................222 Спектральная свертка спасает положение.......................................................................223 Эпилог. От смоделированных спектров – к реальным....................................................227 Зарядные станции..............................................................................................................229 Создание теоретического спектра пептида................................................................229 Насколько быстро выполняется алгоритм CyclopeptideSequencing?........................231 Сокращение списка пептидов Leaderboard.................................................................232 Сопутствующие материалы...............................................................................................233 Гаузе и лысенковщина..................................................................................................233 Открытие кодонов........................................................................................................235 Чувство кворума...........................................................................................................236 Молекулярная масса.....................................................................................................236 Сленоцистеин и пирролизин.......................................................................................237 Псевдополиномиальный алгоритм для Теоремы магистрали..................................237 Расщепленные гены.....................................................................................................238 Библиографические примечания......................................................................................240 Глава 5. Как мы сравниваем участки ДНК?...............................241 Взлом нерибосомного кода...............................................................................................242 Клуб галстуков РНК.......................................................................................................242 От сравнения белков к нерибосомному коду.............................................................242 Что общего между онкогенами и факторами роста?.................................................244 Введение в выравнивание последовательностей............................................................245 Выравнивание последовательности как игра.............................................................245 Выравнивание последовательностей и самая длинная общая подпоследовательность................................................................................................247 Туристическая задача Манхэттена...................................................................................248 Какова наилучшая стратегия осмотра достопримечательностей?...........................248
Содержание 9 Достопримечательности в произвольном ориентированном графе........................252 Выравнивание последовательности – это замаскированная туристическая задача Манхэттена........................................................................................................253 Введение в динамическое программирование: задача размена монет.........................257 Жадный обмен денег....................................................................................................257 Рекурсивный размен денег..........................................................................................258 Размениваем деньги с помощью динамического программирования....................259 Новый взгляд на туристическую задачу Манхэттена................................................261 От Манхэттена к произвольному DAG..............................................................................266 Выравнивание последовательности как построение графа в стиле Манхэттена....266 Динамическое программирование в произвольном графе DAG...............................267 Топологические порядки.............................................................................................269 Возвращаясь к графу выравнивания.................................................................................274 Считаем выравнивания.....................................................................................................277 Что не так с моделью LCS?...........................................................................................277 Матрицы счета..............................................................................................................279 От глобального к локальному выравниванию.................................................................280 Глобальное выравнивание...........................................................................................280 Ограничения глобального выравнивания..................................................................281 Бесплатные поездки на такси в графе выравнивания...............................................284 Меняющиеся грани выравнивания последовательности................................................287 Задача 1. Расстояние редактирования........................................................................287 Задача 2. Настройка выравнивания............................................................................288 Задача 3. Выравнивание с перекрытием....................................................................289 Штрафы за вставки и удаления при выравнивании последовательности.....................290 Штрафы за аффинные пробелы...................................................................................290 Строительство графа Манхэттена на трех уровнях....................................................293 Компактное выравнивание последовательности............................................................296 Вычисление счета выравнивания с использованием линейной памяти.................296 Задача среднего узла....................................................................................................298 Удивительно быстрый и экономичный алгоритм выравнивания............................301 Задача среднего ребра..................................................................................................303 Эпилог. Множественное выравнивание последовательностей......................................305 Построение трехмерного Манхэттена........................................................................305 Жадный алгоритм множественного выравнивания..................................................307 Сопутствующие материалы...............................................................................................310 Светлячки и нерибосомный код..................................................................................310 Поиск LCS без постройки города.................................................................................311 Построение топологической сортировки...................................................................312 Матрица счета PAM.......................................................................................................313 Алгоритмы «разделяй и властвуй»..............................................................................314 Счет множественных выравниваний..........................................................................316 Библиографические примечания......................................................................................318 Глава 6. Есть ли в человеческом геноме «хрупкие» области?......................................................................................................................319 О мышах и людях...............................................................................................................320 Насколько различаются геномы человека и мыши?..................................................321 Синтенные блоки..........................................................................................................321
10 Содержание Реверсии........................................................................................................................322 Точки перестановки.....................................................................................................324 Модель эволюции хромосом со случайными разрывами...............................................325 Сортировка по реверсиям..................................................................................................328 Жадный алгоритм сортировки по реверсиям..................................................................332 Точки останова...................................................................................................................334 Что такое точки останова?...........................................................................................334 Счет точек останова......................................................................................................335 Сортировка по реверсиям для устранения точек останова.......................................336 Рекомбинации в геномах опухолей..................................................................................338 От монохромосомных к мультихромосомным геномам.................................................339 Транслокации, слияния и расщепления.....................................................................339 От генома к графу.........................................................................................................340 Двойные разрывы.........................................................................................................341 Графы точек останова........................................................................................................344 Вычисление дистанции двойного разрыва......................................................................347 Горячие точки рекомбинации в геноме человека............................................................350 Модель случайных разрывов соответствует теореме о дистанции двойного разрыва..........................................................................................................................350 Модель хрупких разрывов............................................................................................351 Эпилог. Конструирование синтенных блоков..................................................................353 Геномные точечные диаграммы и общие k-меры......................................................353 Поиск общих k-меров...................................................................................................354 Построение синтенных блоков из общих k-меров.....................................................357 Синтенные блоки как связные компоненты в графах...............................................359 Зарядные станции..............................................................................................................363 От геномов к графу точек останова.............................................................................363 Решение задачи сортировки по двойным разрывам.................................................366 Сопутствующие материалы...............................................................................................368 Почему генный состав Х-хромосом так консервативен?...........................................368 Открытие геномных рекомбинаций...........................................................................368 Экспоненциальное распределение.............................................................................369 Сортировка блинов Билла Гейтса и Дэвида X. Коэна.................................................370 Сортировка линейных перестановок по реверсиям..................................................371 Библиографические примечания......................................................................................373 Глава 7. Какое животное заразило нас коронавирусом?..................................................................................................375 Самая быстрая вспышка....................................................................................................376 Проблемы в отеле «Метрополь»...................................................................................376 Эволюция SARS.............................................................................................................376 Преобразование матриц расстояний в эволюционные деревья.....................................378 Построение матрицы расстояний из геномов коронавируса....................................378 Эволюционные деревья в виде графов.......................................................................379 Построение филогении по расстояниям.....................................................................383 На пути к алгоритму построения филогении по расстоянию.........................................386 В поисках соседних листьев.........................................................................................386 Вычисление длины ветвей...........................................................................................388 Аддитивная филогения......................................................................................................391