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

последовательности.....................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
Экспоненциальное --">