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

Перед вами одно из самых популярных за рубежом руководств по биоинформатике. Книга обеспечивает уникальный баланс между практическими задачами современной биологии и фундаментальными алгоритмическими идеями. Каждая глава начинается с биологического вопроса, а затем неуклонно развивается алгоритмическая сложность, необходимая для ответа на него. Сотни упражнений включены непосредственно в текст и помогают разобраться в непростом материале.

Издание предназначено специалистам в области анализа данных, а также будет полезно ученым, инженерам, студентам и аспирантам, работающим на стыке биологии и информатики.
В каком месте генома начинается репликация ДНК?
Путешествие в тысячу миль…
Скрытые сообщения в точке начала репликации
DnaA-боксы
Скрытые сообщения в «Золотом жуке»
Подсчет слов
Задача поиска часто встречающихся слов
Более быстрый подход к задаче частых слов
Часто используемые слова в Vibrio cholerae
Некоторые скрытые сообщения более примечательны, чем другие
Взрыв скрытых сообщений
Поиск скрытых сообщений в нескольких геномах
Задача поиска сгустков
Самое простое объяснение процесса репликации ДНК
Асимметрия репликации
Специфическая статистика прямой и обратной полуцепей
Неизвестный биологический феномен или статистическая случайность?
Дезаминирование
Диаграмма смещения
Некоторые скрытые сообщения более неуловимы, чем другие
Последняя попытка найти DnaA-боксы в E. Coli
Эпилог. Осложнения в предсказаниях ori
Открытые проблемы
Множественные точки начала репликации в бактериальном геноме
Поиск источников репликации у архей
Поиск точек начала репликации у дрожжей
Вычисление вероятностей паттернов в строке
Зарядные станции
Массив частот
Преобразование Patterns в Numbers и наоборот
Поиск часто встречающихся слов путем сортировки
Решение задачи поиска сгустков
Решение задачи часто встречающихся слов с несовпадениями
Генерация окрестности строки
Поиск часто встречающихся слов с несовпадениями путем сортировки
Сопутствующие материалы
Оценка «О большого» (Big-O)
Вероятности паттернов в строке
Самый красивый эксперимент в биологии
Направленность цепей ДНК
Ханойские башни
Парадокс перекрывающихся слов
Библиографические примечания
Какие сегменты ДНК играют роль молекулярных часов?
Есть ли у нас «часовой ген»?
Найти мотив сложнее, чем вы думаете
Идентификация вечернего элемента
Игра в прятки с мотивами
Метод грубой силы поиска мотива
Считаем мотивы
От мотивов к матрицам профиля и консенсусным строкам
На пути к более адекватной функции оценки мотивов
Энтропия и motif logo
От поиска мотива к поиску медианной строки
Задача поиска мотива
Переформулировка задачи поиска мотива
Задача поиска медианной строки
Почему мы переформулировали задачу поиска мотива?
Жадный алгоритм поиска мотива
Использование матрицы профиля для бросания костей
Анализ жадного алгоритма поиска мотива
Поиск мотива и Оливер Кромвель
Какова вероятность того, что завтра не взойдет солнце?
Правило преемственности Лапласа
Улучшенный алгоритм жадного поиска мотивов
Рандомизированный поиск мотива
Игра в кости для поиска мотивов
Почему рандомизированный поиск мотивов работает
Почему рандомизированный алгоритм работает так хорошо?
Сэмплирование по Гиббсу
Сэмплирование по Гиббсу в действии
Эпилог. Как туберкулез впадает в спячку, чтобы спрятаться от антибиотиков?
Зарядная станция
Решение задачи медианной строки
Сопутствующие материалы
Экспрессия генов
ДНК-чипы
Игла Бюффона
Сложности в поиске мотива
Относительная энтропия
Библиографические примечания
Как мы собираем геномы?
Взрывающиеся газеты
Задача реконструкции строки
Сборка генома сложнее, чем вы думаете
Реконструкция строк из k-меров
Повторы усложняют сборку генома
Реконструкция строк как прогулка по графу перекрытий
От строки к графу
Геном исчезает
Два способа представления графов
Гамильтоновы пути и универсальные строки
Другой граф для реконструкции строк
Склеивание узлов и графы де Брюйна
Прогулка по графу де Брюйна
Эйлеровы пути
Другой способ построения графов де Брюйна
Построение графов де Брюйна из композиции k-меров
Графы де Брюйна в сравнении с графами перекрытия
Семь мостов Кенигсберга
Теорема Эйлера
От теоремы Эйлера к алгоритму нахождения эйлеровых циклов
Построение эйлеровых циклов
От эйлеровых циклов к эйлеровым путям
Создание универсальных строк
Сборка геномов из рид-пар
От ридов к рид-парам
Преобразование рид-пар в длинные виртуальные риды
От композиции к спаренной композиции
Парные графы графы де Брюйна
Ловушка парных графов де Брюйна
Эпилог. Сборка генома – работа с реальными данными секвенирования
Разбиваем риды на k-меры
Фрагментация генома на контиги
Сборка ридов с возможными ошибками
Определение кратности ребер в графах де Брюйна
Зарядные станции
Влияние склейки на матрицу смежности
Генерация всех эйлеровых циклов
Реконструкция строки, записанной как путь в парном графе де Брюйна
Максимальные неветвящиеся пути в графе
Сопутствующие материалы
Краткая история технологий секвенирования ДНК
Повторы в геноме человека
Графы
Игра «Икосиан»
Разрешимые и неразрешимые задачи
От Эйлера до Гамильтона и де Брюйна
Семь мостов Калининграда
Подводные камни сборки двухцепочечной ДНК
«ЛУЧШАЯ» теорема
Библиографические примечания
Как мы секвенируем антибиотики?
Открытие антибиотиков
Как бактерии производят антибиотики?
Как пептиды кодируются геномом
Где в геноме Bacillus brevis закодирован тироцидин?
От линейных к циклическим пептидам
Уклоняясь от центральной догмы молекулярной биологии
Секвенирование антибиотиков путем их дробления на части
Введение в масс-спектрометрию
Задача секвенирования циклопептидов
Алгоритм грубой силы для секвенирования циклопептидов
Алгоритм ветвей и границ для секвенирования циклопептидов
Масс-спектрометрия и гольф
От теоретических к реальным спектрам
Адаптация секвенирования циклопептидов для спектров с ошибками
От 20 до более чем 100 аминокислот
Спектральная свертка спасает положение
Эпилог. От смоделированных спектров – к реальным
Зарядные станции
Создание теоретического спектра пептида
Насколько быстро выполняется алгоритм CyclopeptideSequencing?
Сокращение списка пептидов Leaderboard
Сопутствующие материалы
Гаузе и лысенковщина
Открытие кодонов
Чувство кворума
Молекулярная масса
Сленоцистеин и пирролизин
Псевдополиномиальный алгоритм для Теоремы магистрали
Расщепленные гены
Библиографические примечания
Как мы сравниваем участки ДНК?
Взлом нерибосомного кода
Клуб галстуков РНК
От сравнения белков к нерибосомному коду
Что общего между онкогенами и факторами роста?
Введение в выравнивание последовательностей
Выравнивание последовательности как игра
Выравнивание последовательностей и самая длинная общая подпоследовательность
Туристическая задача Манхэттена
Какова наилучшая стратегия осмотра достопримечательностей?
Достопримечательности в произвольном ориентированном графе
Выравнивание последовательности – это замаскированная туристическая задача Манхэттена
Введение в динамическое программирование: задача размена монет
Жадный обмен денег
Рекурсивный размен денег
Размениваем деньги с помощью динамического программирования
Новый взгляд на туристическую задачу Манхэттена
От Манхэттена к произвольному DAG
Выравнивание последовательности как построение графа в стиле Манхэттена
Динамическое программирование в произвольном графе DAG
Топологические порядки
Возвращаясь к графу выравнивания
Считаем выравнивания
Что не так с моделью LCS?
Матрицы счета
От глобального к локальному выравниванию
Глобальное выравнивание
Ограничения глобального выравнивания
Бесплатные поездки на такси в графе выравнивания
Меняющиеся грани выравнивания последовательности
Задача 1. Расстояние редактирования
Задача 2. Настройка выравнивания
Задача 3. Выравнивание с перекрытием
Штрафы за вставки и удаления при выравнивании последовательности
Штрафы за аффинные пробелы
Строительство графа Манхэттена на трех уровнях
Компактное выравнивание последовательности
Вычисление счета выравнивания с использованием линейной памяти
Задача среднего узла
Удивительно быстрый и экономичный алгоритм выравнивания
Задача среднего ребра
Эпилог. Множественное выравнивание последовательностей
Построение трехмерного Манхэттена
Жадный алгоритм множественного выравнивания
Сопутствующие материалы
Светлячки и нерибосомный код
Поиск LCS без постройки города
Построение топологической сортировки
Матрица счета PAM
Алгоритмы «разделяй и властвуй»
Счет множественных выравниваний
Библиографические примечания
Есть ли в человеческом геноме «хрупкие» области?
О мышах и людях
Насколько различаются геномы человека и мыши?
Синтенные блоки
Реверсии
Точки перестановки
Модель эволюции хромосом со случайными разрывами
Сортировка по реверсиям
Жадный алгоритм сортировки по реверсиям
Точки останова
Что такое точки останова?
Счет точек останова
Сортировка по реверсиям для устранения точек останова
Рекомбинации в геномах опухолей
От монохромосомных к мультихромосомным геномам
Транслокации, слияния и расщепления
От генома к графу
Двойные разрывы
Графы точек останова
Вычисление дистанции двойного разрыва
Горячие точки рекомбинации в геноме человека
Модель случайных разрывов соответствует теореме о дистанции двойного разрыва
Модель хрупких разрывов
Эпилог. Конструирование синтенных блоков
Геномные точечные диаграммы и общие k-меры
Поиск общих k-меров
Построение синтенных блоков из общих k-меров
Синтенные блоки как связные компоненты в графах
Зарядные станции
От геномов к графу точек останова
Решение задачи сортировки по двойным разрывам
Сопутствующие материалы
Почему генный состав Х-хромосом так консервативен?
Открытие геномных рекомбинаций
Экспоненциальное распределение
Сортировка блинов Билла Гейтса и Дэвида X. Коэна
Сортировка линейных перестановок по реверсиям
Библиографические примечания
Какое животное заразило нас коронавирусом?
Самая быстрая вспышка
Проблемы в отеле «Метрополь»
Эволюция SARS
Преобразование матриц расстояний в эволюционные деревья
Построение матрицы расстояний из геномов коронавируса
Эволюционные деревья в виде графов
Построение филогении по расстояниям
На пути к алгоритму построения филогении по расстоянию
В поисках соседних листьев
Вычисление длины ветвей
Аддитивная филогения
Обрезка дерева
Прикрепление ветви
Алгоритм реконструкции филогении по расстоянию
Построение эволюционного дерева коронавирусов
Использование метода наименьших квадратов для построения приблизительных филогений
Ультраметрические эволюционные деревья
Алгоритм объединения соседей
Преобразование матрицы расстояний в матрицу объединения соседей
Анализ коронавирусов с помощью алгоритма объединения соседей
Ограничения методов реконструкции эволюционного дерева по расстояниям
Реконструкция эволюционного дерева по признакам
Таблицы признаков
От анатомических к генетическим признакам
Сколько раз эволюция изобретала крылья для насекомых?
Задача минимального показателя экономии
Задача максимальной экономии
Эпилог. Эволюционные деревья в борьбе с преступностью
Сопутствующие материалы
Когда HIV перешел от приматов к человеку?
Поиск дерева с помощью настройки матрицы расстояний
Условие четырех точек
Заразили ли нас атипичной пневмонией летучие мыши?
Почему алгоритм объединения соседей работает?
Вычисление длин ветвей в алгоритме объединения соседей
Большая панда: медведь или енот?
Откуда пришли люди?
Библиографические примечания
Как дрожжи научились делать вино?
Эволюционная история виноделия
Как давно мы зависим от алкоголя?
Диауксический сдвиг
Идентификация генов, ответственных за диауксический сдвиг
Две эволюционные гипотезы с разными судьбами
Какие гены дрожжей вызывают диауксический сдвиг
Введение в кластеризацию
Анализ экспрессии генов
Кластеризация генов дрожжей
Принцип правильной кластеризации
Кластеризация как задача оптимизации
Самый дальний первый обход
Самый дальний первый обход
Кластеризация k-средних
Искажение квадрата ошибки
Кластеризация k-средних и центр тяжести
Алгоритм Ллойда
От центров к кластерам и обратно
Инициализация алгоритма Ллойда
Инициализатор k-means++
Кластеризация генов, вовлеченных в диауксический сдвиг
Ограничения кластеризации k-средних
Ограничения кластеризации k-средних
От подбрасывания монеты к кластеризации k-средних
Подбрасывание монет с неизвестной симметрией
В чем же состоит вычислительная задача?
От подбрасывания монеты к алгоритму Ллойда
Вернемся к кластеризации
Принятие мягких решений при подбрасывании монет
Максимизация ожиданий: Е-шаг
Максимизация ожиданий: М-шаг
Алгоритм максимизации ожидания
Мягкая кластеризация k-средних
Применение алгоритма максимизации ожидания к кластеризации
От центров к мягким кластерам
От мягких кластеров к центрам
Иерархическая кластеризация
Введение в кластеризацию по расстояниям
Определение кластеров по структуре дерева
Анализ диауксического сдвига с иерархической кластеризацией
Эпилог. Кластеризация образцов опухоли
Сопутствующие материалы
Полногеномная дупликация или серия дупликаций?
Измерение экспрессии генов
ДНК-микрочипы
Доказательство теоремы о центре тяжести
Матрица экспрессии генов и матрица расстояний/сходств
Кластеризация и испорченные клики
Библиографические примечания
Как мы обнаруживаем локацию болезнетворных мутаций?
Что вызывает синдром Одо?
Введение во множественное выравнивание последовательностей
Объединение Patterns в префиксное дерево
Построение префиксного дерева Trie
Применение префиксного дерева к множественному выравниванию
Предварительная обработка генома как альтернатива
Суффиксные попытки (suffix tries)
Использование суффиксных попыток для сопоставления последовательностей
Суффиксные деревья (suffix trees)
Суффиксные массивы
Выравнивание паттерна с суффиксным массивом
Преобразование Барроуза–Уилера
Сжатие генома
Построение преобразования Барроуза–Уилера
От повторов к сериям
Первая попытка инвертирования преобразования Барроуза–Уилера
Свойство «первый–последний» и инвертирование преобразования Барроуза–Уилера
Свойство «первый–последний»
Использование свойства «первый–последний» для инвертирования преобразования Барроуза–Уилера
Сопоставление последовательностей с помощью преобразования Барроуза–Уилера
Первая попытка сопоставления паттернов Барроуза–Уилера
Перемещение по последовательности назад
Маппинг «последний–первый»
Делаем сопоставление паттернов по Барроузу–Уилеру быстрее
Замена маппинга «последний–первый» оценочными массивами
Удаление первого столбца матрицы Барроуза–Уилера
Где находятся совпадающие паттерны?
Барроуз и Уиллер устанавливают контрольные точки
Эпилог. Устойчивое к несовпадениям картирование рида
Сведение приблизительного сопоставления с паттерном к точному
BLAST: Сравнение последовательности с базой данных
Приблизительное сопоставление последовательностей с помощью преобразования Барроуза–Уилера
Сопутствующие материалы
Построение суффиксного дерева
Решение задачи самой длинной общей подстроки
Построение частичного суффиксного массива
Эталонный геном человека
Рекомбинации, вставки и делеции в геномах человека
Алгоритм Ахо–Корасик
Суффиксные массивы и суффиксные деревья
Бинарный поиск
Библиографические примечания
Почему биологи до сих пор не разработали вакцину от ВИЧ?
Классификация фенотипа ВИЧ
Каким образом ВИЧ ускользает от иммунной системы человека?
Ограничения метода выравнивания последовательностей
Азартные игры с якудза
Две монеты в рукаве у дилера
Поиск CG-островов
Скрытые марковские модели
От подбрасывания монеты к скрытой марковской модели
Диаграмма НММ
Переформулировка задачи казино
Задача декодирования
Граф Витерби
Алгоритм Витерби
Насколько быстр алгоритм Витерби?
Поиск наиболее вероятного результата HMM
Профильные HMM для выравнивания последовательностей
Как НММ связаны с выравниванием последовательностей?
Создание профильной НММ
Вероятности перехода и эмиссии профильной HMM
Классификация белков с помощью профильных HMM
Выравнивание белков по профильной HMM
Возвращение псевдосчетов
Проблема с молчащими состояниями
Действительно ли профильные HMM так полезны?
Обучение параметров HMM
Определение параметров HMM, когда скрытый путь известен
Обучение Витерби
Мягкие решения для определения параметров
Задача мягкого декодирования
Алгоритм «вперед–назад»
Обучение Баума–Уэлча
Многоликость HMM
Эпилог. Природа – мастер, а не изобретатель
Сопутствующие материалы
Эффект Красной Королевы
Гликозилирование
Метилирование ДНК
Условная вероятность
Библиографические примечания
Является ли T. rex всего лишь гигантской курицей?
Палеонтология встречается с информатикой
Какие белки присутствуют в этом образце?
Расшифровка идеального спектра
От идеального спектра к реальному
Секвенирование пептидов
Определение пептидов по спектрам
Где находятся суффиксные пептиды?
Алгоритм секвенирования пептидов
Идентификация пептидов
Задача идентификации пептидов
Идентификация пептидов в неизвестном протеоме T. rex
Поиск совпадений пептидов со спектром
Идентификация пептидов и теорема о бесконечных обезьянах
Частота ложных открытий
Статистическая значимость пептид-спектр-совпадений
Спектральные словари
Пептиды T. rex: постороннее загрязнение или древнее сокровище?
Загадка гемоглобина
Споры о ДНК динозавров
Эпилог. От немодифицированных к модифицированным пептидам. (Часть 1)
Посттрансляционные модификации
Поиск модификаций как задача выравнивания
Построение сетки Манхэттена для спектрального выравнивания
Эпилог. От немодифицированных к модифицированным пептидам (Часть 2)
Алгоритм спектрального выравнивания
Сопутствующие материалы
Предсказание генов
Поиск всех путей в графе
Задача антисимметричного пути
Преобразование спектров в спектральные векторы
Теорема о бесконечных обезьянах
Вероятностное пространство пептидов в словаре
Действительно ли динозавры являются предками птиц?
Библиографические примечания
Предметный указатель