Алгоритмы биоинформатики
Покупка
Тематика:
Общая биология
Издательство:
ДМК Пресс
Перевод:
Люско И. Л.
Год издания: 2023
Кол-во страниц: 684
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
ВО - Специалитет
ISBN: 978-5-93700-175-7
Артикул: 817236.01.99
Перед вами одно из самых популярных за рубежом руководств по биоинформатике. Книга обеспечивает уникальный баланс между практическими задачами современной биологии и фундаментальными алгоритмическими идеями. Каждая глава начинается с биологического вопроса, а затем неуклонно развивается алгоритмическая сложность, необходимая для ответа на него. Сотни упражнений включены непосредственно в текст и помогают разобраться в непростом материале.
Издание предназначено специалистам в области анализа данных, а также будет полезно ученым, инженерам, студентам и аспирантам, работающим на стыке биологии и информатики.
Алгоритмы биоинформатики: путешествие от ДНК к решению биологических загадок
Эта книга, написанная Филиппом Компо и Павлом Певзнером, представляет собой глубокое погружение в мир биоинформатики, рассматривая алгоритмы как ключевой инструмент для решения задач современной биологии. Авторы предлагают уникальный подход, сочетая практические биологические вопросы с фундаментальными алгоритмическими идеями. Каждая глава начинается с биологической проблемы, а затем постепенно раскрывает алгоритмическую сложность, необходимую для ее решения.
Поиск точки начала репликации ДНК
Первая глава посвящена поиску точки начала репликации ДНК (ori) в геноме. Авторы начинают с рассмотрения бактериального генома, где ori обычно имеет длину в несколько сотен нуклеотидов. Они вводят задачу поиска часто встречающихся слов, которая позволяет идентифицировать скрытые сообщения, такие как DnaA-боксы, в области ori. Для решения этой задачи предлагаются алгоритмы, такие как FrequentWords и BetterFrequentWords, а также обсуждается оценка их сложности. Авторы также рассматривают проблему поиска сгустков (clumps) и показывают, как асимметрия репликации, вызванная дезаминированием, может быть использована для локализации ori.
Молекулярные часы и поиск мотивов
Вторая глава фокусируется на идентификации регуляторных мотивов, которые играют роль молекулярных часов. Авторы вводят понятие мотива и рассматривают задачу поиска мотива, которая заключается в поиске наиболее часто встречающихся k-меров в наборе строк. Для решения этой задачи предлагаются различные алгоритмы, включая метод грубой силы, жадный алгоритм и рандомизированный поиск мотивов. Авторы также обсуждают понятие энтропии и использование motif logo для визуализации консервативности мотивов.
Сборка геномов и алгоритмы графов
Третья глава посвящена сборке геномов. Авторы рассматривают задачу реконструкции строки из ее k-мер-композиции и показывают, что повторы в геноме усложняют эту задачу. Для решения этой проблемы они вводят алгоритмы графов, такие как графы перекрытий и графы де Брюйна, и показывают, как использовать эйлеровы пути для сборки генома. Авторы также рассматривают проблему сборки генома из рид-пар.
Секвенирование антибиотиков и динамическое программирование
Четвертая глава посвящена секвенированию антибиотиков. Авторы рассматривают задачу секвенирования циклопептидов и показывают, как использовать алгоритмы грубой силы и ветвей и границ для ее решения. Они также вводят понятие масс-спектрометрии и показывают, как адаптировать алгоритмы секвенирования циклопептидов для спектров с ошибками.
Сравнение участков ДНК и динамическое программирование
Пятая глава посвящена сравнению участков ДНК. Авторы вводят задачу самой длинной общей подпоследовательности (LCS) и показывают, как использовать динамическое программирование для ее решения. Они также рассматривают задачу настройки выравнивания и выравнивания с перекрытием, а также вводят понятие штрафов за вставки и удаления.
Хрупкие области в геноме человека и рекомбинации
Шестая глава посвящена анализу рекомбинаций генома. Авторы вводят понятие синтенных блоков и показывают, как использовать точки останова для вычисления расстояния двойного разрыва между геномами. Они также рассматривают модель случайных разрывов и модель хрупких разрывов.
Эволюционные деревья и кластеризация
Седьмая глава посвящена построению эволюционных деревьев. Авторы вводят понятие матрицы расстояний и показывают, как использовать алгоритм объединения соседей для построения филогении по расстояниям. Они также рассматривают задачу максимальной экономии и показывают, как использовать ее для построения эволюционного дерева по признакам.
Дрожжи и виноделие: кластеризация
Восьмая глава посвящена кластеризации. Авторы вводят задачу кластеризации k-средних и показывают, как использовать алгоритм Ллойда для ее решения. Они также рассматривают иерархическую кластеризацию.
Обнаружение болезнетворных мутаций и комбинаторное выравнивание
Девятая глава посвящена обнаружению локации болезнетворных мутаций. Авторы вводят понятие множественного выравнивания последовательностей и показывают, как использовать префиксные деревья, суффиксные деревья и суффиксные массивы для сопоставления последовательностей. Они также рассматривают преобразование Барроуза–Уилера.
ВИЧ и скрытые марковские модели
Десятая глава посвящена разработке вакцин против ВИЧ. Авторы вводят понятие скрытых марковских моделей (HMM) и показывают, как использовать алгоритм Витерби для декодирования HMM. Они также рассматривают профильные HMM для выравнивания последовательностей и показывают, как использовать обучение Баума–Уэлча для обучения параметров HMM.
T. rex и секвенирование пептидов
Одиннадцатая глава посвящена секвенированию пептидов. Авторы показывают, как использовать масс-спектрометрию для секвенирования пептидов и как использовать алгоритм спектрального выравнивания для идентификации пептидов.
В заключение, книга предоставляет всесторонний обзор алгоритмов биоинформатики, охватывая широкий спектр тем от секвенирования геномов до построения эволюционных деревьев. Она является ценным ресурсом для специалистов в области анализа данных, а также будет полезна ученым, инженерам, студентам и аспирантам, работающим на стыке биологии и информатики.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Филлип Компо и Павел Певзнер Алгоритмы биоинформатики
Bioinformatics Algorithms An Active Learning Approach PHILLIP COMPEAU AND PAVEL PEVZNER
Москва, 2023 Алгоритмы биоинформатики ФИЛЛИП КОМПО И ПАВЕЛ ПЕВЗНЕР
УДК 575.112 ББК 28.071.3 К63 Певзнер П., Компо Ф. К63 Алгоритмы биоинформатики / пер. с англ. И. Л. Люско. – М.: ДМК Пресс, 2023. – 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
Содержание От издательства ...................................................................................................... 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
Содержание Решение задачи поиска сгустков ................................................................................. 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
Содержание От Эйлера до Гамильтона и де Брюйна ......................................................................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
Содержание Реверсии .......................................................................................................................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