Алгоритм поиска клики в графе, предсказание регуляторных структур РНК и моделирование регуляции биосинтеза триптофана

• Автор: Селиверстов, Александр Владиславович
• Шифр специальности: 05.13.17, 03.00.28
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 102 с. : ил.

ОГЛАВЛЕНИЕ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Цели работы

Методы исследования

Научная новизна

Основные результаты

Практическая значимость работы

Апробация работы

Публикации

Структура и объем работы

ВВЕДЕНИЕ
0.1 Обзор алгоритмических результатов, относящихся к
диссертационному исследованию
0.2 Обзор результатов по регуляции экспрессии генов у хлоропластов и бактерий
0 3 Обзор результатов по моделированию кинетики образования вторичной структуры РНК
ГЛАВА 1. Алгоритм поиска клики в многодольном графе
1.1. Алгоритм поиска клики в случае двух вершин в каждой доле и
доказательство корректности его работы за полиномиальное время
1 2 Алгоритм решения неявно заданной системы однородных линейных уравнений над конечным бимодулем и нижняя оценка
числа клик
1 3. Алгоритм поиска клики в многодольном графе в общем случае и поиск консервативных участков в невыравненном наборе последовательностей на основе этого алгоритма, учет дерева видов 1 4. Тестирование алгоритма
1.5. Вспомогательные программы для выделения лидерных областей
генов и поиска спиралей и слов специального вида по их параметрам в аннотированных геномах
ГЛАВА 2. Предсказание структур РНК, регулирующих
экспрессию генов, у хлоропластов и бактерий на основе алгоритма поиска клики
2 1. Регуляция трансляции посредством взаимодействия белков с
РНК для различных генов у хлоропластов
2.2. Различные системы регуляции экспрессии генов биосинтеза аминокислот и аминоацилтРНК синтетаз у актинобактерий
2 3 Регуляция трансляции гътукоЕ АВС транспортера посредством
тиаминового рибопереключателя у актинобактерий
2.4. Регуляция трансляции гена аг0б с участием Тбокса у
цианобактерии АЬбюс РСС7
ГЛАВА 3. Моделирование классической аггенюаторной
регуляции биосинтеза триптофана у бакгерий
3.1. Математическая модель классической аггенюаторной регуляции
3.2 Проверка модели методом МонтеКарло
3.3. Тестирование модели и обсуждение результатов
ОСНОВНЫЕ РЕЗУЛЬТАТЫ
СПИСОК ЛИТЕРАТУРЫ


Эти консервативные участки составляют упомянутые выше регуляторные структуры (сигналы) - статику регуляции экспрессии соответствующих генов Однако практическое применение этого подхода затруднялось из-за отсутствия эффективных методов поиска клики. Другие методы поиска сигнала рассмотрены в работах А А. Миронова, ПА Певзнера, М. С. Уотермена и др. Альтернативный путь изучения регуляторных структур по одной последовательности РНК, впервые рассмотренный А А. Мироновым, состоит в моделировании кинетики вторичной структуры РНК. Однако, многие регуляторные системы, включая классическую аттенюаторную регуляцию экспрессии генов, не исследовались подобным образом. И после уточнения модели - решение вопроса о наличии регуляции в одной лидерной области, без множественного выравнивания и поиска сигналов, что представляет собой весьма трудную задачу. Цели работы. Методы исследования. Научная новизна. Разработаны алгоритмы для поиска клики в многодольном графе, исследована их вычислительная сложность и предсказаны как новые потенциальные типы регуляции экспрессии генов на уровнях трансляции и транскрипции, так и много новых потенциальных регуляторных структур перед отдельными генами Положения, выносимые на защит)'. Доказано, что существование «-клики в «-дольном графе с двумя вершинами в каждой доле эквивалентно непустоте многогранника, стороны которого вычисляются за полиномиальное от « время. Таким образом, предложен алгоритм поиска клики в указанном многодольном графе с помощью алгоритма линейного программирования. Разработан алгоритм полиномиального времени для решения неявно заданной системы однородных линейных уравнений над конечным бимодулем и математически доказана его корректность. Алгоритм позволяет, в частности, оценивать снизу число клик в многодольном графе. С помощью этого эвристического алгоритма найдены новые потенциальные сайты связывания белков с мРНК у хлоропластов в 5’-нетранслируемых областях генов atpF> clpP, petB и генов psaA, psbA, psbB, кодирующих белки фотосистем. Предложена гипотеза, объясняющая задержку начала трансляции до завершения сплайсинга у ряда этих генов за счет специального белок-РНКового связывания. Corynebactenum и Streptomyces; гена trpS, кодирующего триптофанил-тРНК синтетазу, у Streptomyces avemittlts, генов ieuS, кодирующих лейцил-тРНК синтетазу, у Streptomyces; оперонов ilv у многих актинобактерий Предсказаны у многих актинобактерий' новый потенциальный тип регуляции трансляции гена 1еиА, кодирующего 2-изопропилмалат синтазу, Т-боксовая регуляция трансляции гена ileS, кодирующего изолейцил-тРНК синтетазу, потенциальная Rho-зависимая аттенюаторная регуляция биосинтеза цистеина. Практическая значимость работы. Работа носит теоретический характер. В то же время, данное исследование представляет интерес, поскольку сравнительный анализ геномов позволяет лучше понять механизмы возникновения устойчивости бактерий к антибиотикам и найти пути создания более эффективных промышленных штаммов Компьютерный анализ проведен в части регуляции экспрессии перечисленных выше генов. К актинобактериям принадлежат индустриальные продуценты аминокислот (Corynebactenum glutamtcum, Corynebactenum efficiens) и антибиотиков (Streptomyces spp. Mycobacterium spp. В то же время актинобактерии составляют отдельную филогенетическую группу, и они исследованы гораздо меньше, чем кишечная палочка (представитель протеобактерий) или сенная палочка (представитель фирмикутов). В случае хлоропластов предложена гипотеза, объясняющая задержку начала трансляции до завершения сплайсинга для многих генов за счет белок-РНКового связывания, что может представлять интерес для изучения сплайсинга у других организмов и также углубленного изучения процессов фотосинтеза у водорослей и растений на геномном уровне. Предложенные алгоритмы и программа поиска клики и сигнала могут быть применены для исследования широкого класса задач. Аппробация работы Результаты диссертации неоднократно излагались на семинаре Учебно-Научного центра «Биоинформатика» Института проблем передачи информации РАН, на семинаре «Алгоритмы в геномике» кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им.