Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Алгоритмы биоинформатики

Покупка
Артикул: 817236.01.99
Перед вами одно из самых популярных за рубежом руководств по биоинформатике. Книга обеспечивает уникальный баланс между практическими задачами современной биологии и фундаментальными алгоритмическими идеями. Каждая глава начинается с биологического вопроса, а затем неуклонно развивается алгоритмическая сложность, необходимая для ответа на него. Сотни упражнений включены непосредственно в текст и помогают разобраться в непростом материале. Издание предназначено специалистам в области анализа данных, а также будет полезно ученым, инженерам, студентам и аспирантам, работающим на стыке биологии и информатики.
17
87
135
201
241
319
334
375
443
503
567
623
Компо, Ф. Алгоритмы биоинформатики : практическое руководство / Ф. Компо, П. Певзнер ; пер. с англ. И. Л. Люско. - Москва : ДМК Пресс, 2023. - 684 с. - ISBN 978-5-93700-175-7. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2109518 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Филлип Компо и Павел Певзнер
Алгоритмы биоинформатики


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