Введение к работе
Актуальность проблемы. При интенсивном накоплении расшифрованных нуклеотидных и аминокислотных последовательностей из различных геномов, их классификация становится одной из наиболее актуальных проблем молекулярной биологии и генетики. Такая классификация может использоваться, как для определения функциональной принадлежности набора последовательностей, (поиск структурно/функционально важных участков при сравнении анализируемой последовательности с набором, для которого уже получена такая информация), так и для выявления картины эволюционных взаимоотношений (построение филогенетических деревьев). Кроме того, в последнее время все большее значение приобретает другая, родственная классификации задача: определение степени сходства последовательности с другоими последовательностями. Актуальность последней задачи обусловливается широким распространением практики поиска сходства в базах данных. Почти каждая вновь расшифрованная последовательность проходит теперь через такую процедуру. Результаты такого поиска часто позволяют понять функциональное назначение последовательности, то есть отнести ее к группе с известными характеристиками. Во всяком случае, почти всегда такое сравнение позволяет сформулировать следующие вопросы и планировать дальнейшую работу.
Существует два аспекта проблемы поиска сходства п базах данных: алгоритм поиска (обычно выравнивание) и выяснение, действительно ли найденное сходство имеет значение (взвешивание результата). Очевидно, что алгоритм поиска важен сам по себе. Менее хорошо осознается важность соответствующей ему меры взвешивания, без которой даже самый лучший и точный алгоритм сравнения не может дать ничего. Когда для оценки качества выравнивания нельзя привлечь деталыгую биологаческую информацию (например, о вторичной структуре сравниваемых белков), как это, например, происходит при поиске сходства в базе данных, могут быть использованы только 'статистические методы оценки качества наблюдаемого сходства. Поэтому разработка точных методов оценки качества наблюдаемого сходства имеет огромное значение.
Существующие к настоящему времени методы сравнения и классификации дают более или менее приемлемые результаты только в довольно узких интервалах всего разнообразия типов исследуемых последовательностей. Одни применимы только для случая явной гомологии, другие - для слабой, третьим требуется, информация о вторичной структуре белка, четвертые дают приемлемые результаты только в случае примерного равенства длин сравниваемых/классифицируемых последовательностей и т.д. В результате поставленная задача обрастает многочисленными трудностями. Решение ее, как правило, требует много времени, длительного перебора различных методов и вариантов их работы. Чтобы получить наилучший результат исследователю приходится, используя некоторые априорные знания, субъективно принимать решения, что не всегда может быть возможно (при поиске сходства в базе данных). Одним словом, несмотря на наличие большого числа методов сравнения и кластеризации последовательностей, получить
правильный результат для данной последовательности или группы последовательностей фактически может только эксперт (по этим последовательностям). Поэтому появление методов, позволяющих быстро и с высокой точностью осуществлять сравнение, классификацию и, в конечном счете, кластеризацию предложенных последовательностей без каких либо дополнительных знаний о них, будет трудно переоценить. Особенно следует принять во внимание то, что все существующие подходы даже в лучших своих решениях дают невысокое качество (по нашей субъективной оценке от 3 до 4 по 5-ти бальной системе) и имеют очень узкую область применения (как минимум, требуют наличия сильно гомологичных участков в любой из пар последовательностей).
Цели и задачи исследования. Пергой целью работы было создание метода классификации последовательностей биополимеров. Метод должен быть нечувствителен к типу и виду последовательности, которую приходится анализировать, или, по крайней мере, диапазон его применения должен быть очень широк. Второе требование - это его реалистичность, то есть результат кластеризации и полученного множественного выравнивания должен удовлетворять человека - эксперта. Третье требование к методу состоит в том что программа его реализующая должна проводить кластеризацию за разумное время (секунды - минуты).
Вторая цель заключается в разработке более быстрого и чуть менее точного метода определения близости последовательностей, и дальнейшему построению их дендрограммы сходства, основываясь на близости L-плетного состава.
Третья цель - разработка аппарата оценки статистической значимости наблюдаемого сходства блока выравненных последовательностей, учитывающей внутреннюю неоднородность компонент, составляющих блок. Применение этих оценок при решении первой задачи.
Четвертая цель - разработка аппарата оценки статистической значимости качества наблюдаемого выравнивания двух обобщенных последовательностей произвольного состава, учитывающего как их длины, так и их неоднородность; применение этих оценок при решении пергой задачи. Использование результата в поиске по банкам данных.
Мегодьі исследования. Для кластеризации последовательностей в процессе множественного выравнивания использовался обобщенный алгоритм выравнивания, предложенный Селедцовым И.А., Вульфом Ю.И. и Макаровой К.С. (1995).
Научная новизна практическая ценность. Разработан высокоэффективный алгоритм построения дендрограммы сходства последовательностей биополимеров. Алгоритм свободен от многих недостатков предшествующих методов и может быть использован для обработки самых различных по степени схожести последовательностей. Реализующая алгоритм программа применима для решения широкого класса задач, от построения филогенетических деревьев, до выявления структурно/функционально важных областей в последовательностях РНК, ДНК и белков. Показана возможность сравнения меж собой оценок качества выравниваний, образованных последовательностями различной мощности. До настоящего зреме-
ни это ие делалось из-за опасности того, что эти величины окажутся несравнимыми. Предложена схема кластеризации и множественного выравнивания, расширяющая и обобщающая методику прогрессивного выравнивания.
Разработан алгоритм построения дендрограмм сходства последовательностей на основе частот встречаемости определенных олигонуклеотидов или олигопети-дов. Показана высокая точность и чувствительность метода. Ранее дендрограммы сходства, использующие такую меру близости, либо не строились, либо строились, но использовались лишь для целей предварительной классификации.
Впервые введена и обоснована мера внутренней гетерогенности {МВГ) блока выравненных последовательностей. Полученная нами мера обладает рядом важных и интересных свойств, например, относительной независимостью от конкретной матрицы сходства символов.
Опираясь на эту меру, нами предложена двухкомпонентная модель представления одной позиции выравнивания. Показано, что результат множественного выравнивания аминокислотных последовательностей хорошо описывается этой двухкомпонентной моделью. Впервые получена оценка дисперсші величины веса элемента дот-матрицы, опирающаяся только на МВГ, которая весьма точно приближает прямо посчитанную дисперсию.
Получены верхние и нижние асимптотические функции распределения величины веса для фрагмента выравнивания максимального веса Мс. Эти границы задают общий вид функции распределения. Этот результат получен впервые.
Впервые получены асимптотические и аппроксимированы точные выражения для функции распределения (Мс) в зависимости от длины интервала, іде осуществлялся его поиск. Эти точные выражения позволяют, по крайней мере, вдвое поднять точность вычисления статистической значимости наблюдаемого сходства.
Практическая ценность работы" состоит в следующем: а) Реализован алгоритм кластеризации последовательностей, который можно использовать и который уже активно используется в институте для решения различных биологических задач -от целей множественного выравнивания до оценки скоростей эволюции, б) предложен быстрый, точный и свободный от многих недостатков других методов алгоритм поиска аналогов заданной последовательности в базах данных.
Апробация работы. Результаты работы докладывались на 2 международной конференции по Биоинформатике, суперкомпьютерам и комплексному анализу генома, (StPetersburg Beach, Florida, USA, сентябрь 1992 г.), на Втором Сибирском Конгрессе по Прикладной и Индустриальной математике (Новосибирск, июнь 1996г.), а также на отчетных сессиях института Цитологии и Генетики 1993 и 1996г.
Пубяикатии -По теме диссертации опубликовано 4 статьи в рецензируемых изданиях и 5 тезисов докладов на Международных и Российских конференциях.
Структура работы. Работа состоит из следующих разделов: Определения часто используемых понятий. Введения, двух Глав, Заключения и Выводов. Работа изложена на 109 страницах и содержит 5 таблиц и 22 рисунка. Список литерату-