Алгоритмы сравнительного анализа первичных структур биополимеров

• Автор: Ройтберг, Михаил Абрамович
• Шифр специальности: 03.00.28
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Пущино
• Количество страниц: 223 с. : ил.

ОГЛАВЛЕНИЕ
Введение.

1. Обща характеристика работы.

2. Основные понятия и краткий обзор результатов

3. Структура работы.

Глава 1. Обзор литературы.

1.1. Выравнивание символьных последовательностей

1.2. Использование специфики биологических последовательностей

1.3. Выравнивание геномов и построение затравок. .

1.4. Динамическое программирование

Глава 2. Алгоритмы выравнивании символьных последовательностейТ.

2.0. Введение.
2.1. Глобальное выравнивание при кусочнолинейных
штрафах за делеции
2.2. Глобальное выравнивание при штрафах за делеции, пропорциональных длине делеции
2.3. Векторные веса сопоставления символов и Паретооптимальные выравнивания
2.4. Построение биологическикорректного выравнивания
без явного задания штрафов за делеции.
Глава 3. Специализированные алгоритмы выравнивания
биологических последовательностей. г.
3.0. Введение.
3.1. Алгоритмические и структурные выравнивания аминокислотных последовательностей белков.
3.2. Выравнивания аминокислотных последовательностей
с учетом вторичной структуры.
3.3. Выравнивание последовательностей РНК с заданной вторичной структурой.
3.4. Предсказание вторичной структуры РНК
Глава 4. Алгоритмы парного выравнивании, основанные
на выделении локальных сходств.
4.0. Введение.
4.1. Иерархическое выравнивание геномов.
4.2. Алгоритмические задачи, связанные с построением
затравок для поиска локальных сходств.
4.3. Класификационные затравки
Глава 5. Использование обобщенных статистических сумм
для вычисления вероятностей.
5.0. Введение.
5.1. Общий метод вычисления вероятностей семейств
символьных последовательностей.
5.2. Вычисление чувствительности затравок.
5.3. Вероятность обнаружения мотивов в случайных последовательностях
Заключение.
Литература


Вопрос об адекватном выборе значений числовых параметров также решен чисто эмпирически см. Примечательно, что в обзоре i Д. i . i i i вопрос о выборе весов делеций не обсуждается вообще. Пытаясь обойти эту проблему, М. Уотерман и его соавторы рассмотрели задачу о построении субоптимальных имеющих вес, отличающийся от оптимального на заданную величину выравниваний и предложили алгоритм решения этой задачи 7, , см. Практическое применение этого подхода оказалось затрудненным изза тою, что количество субоптимальных выравниваний может быть очень велико даже при очень низком пороге на отличие веса допустимых выравниваний от веса оптимального выравнивания. В то же время рассмотрение семейства выравниваний нашло свое применение при определении степени надежности отдельных выравниваний мера надежности участка оптимального выравнивания определяется количеством субоптимальных выравниваний, содержащих этот участок 0, 0. Наиболее последовательным применением такого подхода является вычисление аналога статистических сумм для графа данного семейства выравниваний вершины графа пары сопоставленных в одном из выравниваний, ребра соединяют соседние сопоставления, см. Эта идея использована в работах М. Лассига и соавторов см. Отмстим, что подобная техника использовалась нами в задаче распознавания кодирующих участков , 2, 0. Взаимосвязь задачи построения оптимального выравнивания и вычисления обобщенных статистических сумм подробно обсуждается в 0, см. В связи с построением субоптимальных выравнивали следует отметить интересную с алгоритмической точки зрения работу 1, посвященную поиску субоптимальных путей в произвольных графах. В работе 3, посвященной выравниваниям иммуноглобулинов, была высказана идея о рассмотрении оптимальных выравниваний как функции весовых параметров, однако алгоритма решения этой задачи предложено не было. Позднее в работах М. Уотермана, Д. Гасфилда и других авторов 1, 9, 1 были предложены алгоритмы декомпозиции пространства параметров на области, соответствующие одному и тому же оптимальному выравниванию. После построения такой декомпозиции все возможные оптимальные выравнивания могут быть найдены с помощью стандартного алгоритма с использованием одного значения параметров для каждой области. В работе 1 дана оценка на количество областей декомпозиции. Кроме того, для задач биоинформатики представляют интерес сами оптимальные выравнивания, а не структура пространства параметров, которой уделяется основное внимание при параметрическом подходе. Подход, представленный в разделе 2. Для того, чтобы получить все потенциально оптимальные выравнивания мы используем многокритериальный подход каждое выравнивание описывается векторным весом компонентами такого вектора могут быть, например, суммарный вес сопоставлений, количество удаленных фрагментов и их суммарная длина. Традиционный вес является линейной комбинацией компонент векторного веса. Этот подход имеет ряд преимуществ перед параметрическим подходом. Вопервых, он позволяет избежать трудоемкого явного построения разбиения пространства параметров на однородные т. Вовторых, в рамках этого подхода естественно формулируется задача о выборе биологически адекватного выравнивания и предлагаются пуги к ес решению. Отмстим, что на основе многокритериального подхода может быть решена задача построения локальных выравниваний максимальной плотности , а также задача построения оптимального выравнивания с заданным количеством удаленных фрагментов 0. Использование специфики биологических последовательностей. Вторичная структура белков и выравнивание аминокислотных последовательностей. В идеале алгоритмическое выравнивание двух биологических последовательностей совпадает с их эволюционным выравниванием, т. В таком выравнивании сопоставленные позиции предположительно происходят от одной и той же позиции последовательности общего предка 6. К сожалению, эволюционные выравнивания нам недоступны.