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

Филлип Компо и Павел Певзнер

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

Bioinformatics
Algorithms
An Active Learning
Approach
P H I L L I P C O M P E A U A N D PAV E L P E V Z N E R

Алгоритмы
биоинформатики
Ф И Л Л И П КО М П О И П А В Е Л П Е В З Н Е Р

Москва, 2023

УДК 575.112
ББК 28.071.3
К63

К63

Певзнер П., Компо Ф.
Алгоритмы биоинформатики / пер. с англ. И. Л. Люско. – М.: ДМК Пресс,
2022. – 682 с.: ил.
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

https://t.me/it_boooks

Содержание
От издательства....................................................................................................... 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
Сопутствующие --">