автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Новые методы сравнения и классификации последовательностей биополимеров

На правах рукописи УДК 578.088:(576.12+575.24)

СЕЛЕДЦОВ ИГОРЬ АЛЕКСЕЕВИЧ

НОВЫЕ МЕТОДЫ СРАВНЕНИЯ II КЛАССИФИКАЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ БИОПОЛИМЕРОВ.

05.13.16 (биол. науки) - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях.

Автореферат

диссертации на соискание ученой степени кандидата биологических наук

Новосибирск 1996 г.

Работа выполнена в Институте цитологии и генетики СО РАН, г. Новосибирск.

Научный руководитель: доктор биологических наук, профессор

В. А. Ратнер,

Институт цитологии и генетики СО РАН, г. Новосибирск

Официальные оппоненты: доктор биологических наук

Е.И. Каракин,

Институт цитологии и генетики СО РАН. г. Новосибирск

кандидат технических наук В.Д. Гусев,

Институт математики СО РАН, г. Новосибирск

Ведущая организация: НИИ Молекулярной Биологии ГНЦ

"Вектор", п. Кольцове.

Защита диссертации состоится " Ь " //(Уа' 1996 г.

на ¿У// ¿¿¿£>/У .заседании специализированного совета по защите диссертаций на соискание ученой степени кандидата наук при Новосибирском институте органической химии СО РАН (К002.42.01) в конференц-зале Института по адресу: 630090, г. Новосибирск - 90, проспект Академика Лаврентьева, 9.

С диссертацией можно ознакомиться в библиотеке Новосибирского института органической химии СО РАН.

Автореферат разослан " 1996 г.

Ученый секретарь специализированного совета, кандидат физико-математических наук > ^ В. И. Смирнов

Актуальность проблемы. При интенсивном накоплении расшифрованных нуклеотидных и аминокислотных последовательностей из различных геномов, их классификация становится одной из наиболее актуальных проблем молекулярной биологии и генетики. Такая классификация может использоваться, как для определения функциональной принадлежности набора последовательностей, (поиск структурно/функционально важных участков при сравнении анализируемой последовательности с набором, для которого уже получена такая информация), так и доя выявления картины эволюционных взаимоотношений (построение филогенетических деревьев). Кроме того, в последнее время все большее значение приобретает другая, родственная классификации задача: определение степени сходства последовательности с другоими последовательностями. Актуальность последней задачи обусловливается широким распространением практики поиска сходства в базах данных. Почти каждая вновь расшифрованная последовательность проходит теперь через такую процедуру. Результаты такого поиска часто позволяют попять функциональное назначение последовательности, то есть отнести ее к группе с известными характеристиками. Во всяком случае, почти всегда такое сравнение позволяет сформулировать следующие вопросы и планировать дальнейшую работу.

Существует два аспекта проблемы поиска сходства и базах данных: алгоритм поиска (обычно выравнивание) и выяснение, действительно ли найденное сходство имеет значение (взвешивание результата). Очевидно, что алгоритм поиска ваЗкен сам по себе. Менее хорошо осознается важность соответствующей ему меры взвешивания, без которой даже самый лучший и точный алгоритм сравнения не может дать ничего. Когда для оценки качества выравнивания нельзя привлечь детальную биологическую информацию (например, о вторичной структуре сравниваемых белков), как это, например, происходит при поиске сходства в базе данных, могут быть использованы только статистические методы оценки качества наблюдаемого сходства Поэтому разработка точных методов оценки качества наблюдаемого сходства имеет огромное значение.

Существующие к настоящему времени методы сравнения и классификации дают более или менее приемлемые результаты только в довольно узких интервалах всего разнообразия типов исследуемых последовательностей. Одни применимы только для случая явной гомологии, другие - для слабой, третьим требуется, информация о вторичной структуре белка, четвертые дают приемлемые результаты только в случае примерного равенства длин сравниваемых/классифицируемых последовательностей и т.д. В результате поставленная задача обрастает многочисленными трудностями. Решение ее, как правило, требует много времени, длительного перебора различных методов и вариантов их работы. Чтобы получить наилучший результат исследователю приходится, используя некоторые априорные знания, субъективно принимать решения, что не всегаа может быть возможно (при поиске сходства в базе данных). Одним словом, несмотря на наличие большого числа методов сравнения и кластеризации последовательностей, получить

правильный результат для данной последовательности или 1руппы последовательностей фактически может только эксперт (по этим последовательностям). Поэтому появление методов, позволяющих быстро и с высокой точностью осуществлять сравнение, классификацию и, в конечном счете, кластеризацию предложенных последовательностей без каких либо дополнительных знаний о них, будет трудно переоценить. Особенно следует принять во внимание то, что все существующие подходы даже в лучших своих решениях дают невысокое качество (по нашей субъективной оценке от 3 до 4 по 5-ти бальной системе) и имеют очень узкую область применения (как минимум, требуют наличия сильно гомологичных участков в любой из пар последовательностей).

Цеди и задачи исследования. Первой целью работы было создание метода классификации последовательностей биополимеров. Метод должен быть нечувствителен к типу и ввду последовательности, которую приходится анализировать, или, по крайней мере, диапазон его применения должен быть очень широк. Второе требование - это его реалистичность, то есть результат кластеризации и полученного множественного выравнивали должен удовлетворять человека - эксперта. Третье требование к методу состоит в том что программа его реализующая должна проводить кластеризацию за разумное время (секунды - минуты).

Вторая цель заключается в разработке более быстрого и чуть менее точного метода определения близости последовательностей, и дальнейшему построению их дендрограммы сходства, основываясь на близости ¿-плетного состава.

Третья цель - разработка аппарата оценки статистической значимости наблюдаемого сходства блока выравненных последовательностей, учитывающей внутреннюю неоднородность компонент, составляющих блок. Применение этих оценок при решении первой задачи.

Четвертая цель - разработка аппарата оценки статистической значимости качества наблюдаемого выравнивания двух обобщенных последовательностей произвольного состава, учитывающего как их длины, так и их неоднородность; применение этих оценок при решении первой задачи. Использование результата в поиске по банкам данных.

Мегодь| исследования. Для кластеризации последовательностей в процессе множественною выравнивания использовался обобщенный алгоритм выравнивания, предложенный Селедцовым И. А., Вульфом Ю.И. и Макаровой К.С. (1995).

Научная новизна практическая ценность. Разработан высокоэффективный алгоритм построения дендрограммы сходства последовательностей биополимеров. Алгоритм свободен от многих недостатков предшествующих методов и может быть использован для обработки самых различных по степени схожести последовательностей. Реализующая алгоритм программа применима для решения широкого класса задач, от построения филогенетических деревьев, до выявления структурно/функционально важных областей в последовательностях РНК, ДНК и белков. Показана возможность сравнения меж собой оценок качества выравниваний, образованных последовательностями различной мощности. До настоящего зреме-

ни это ие делалось из-за опасности того, что эти величины окажутся несравнимыми. Предложена схема кластеризации и множественного выравнивания, расширяющая и обобщающая методику прогрессивного выравнивания.

Разработан алгоритм построения дендрограмм сходства последовательностей на основе частот встречаемости определенных одигонуклеотндов или олигопети-дов. Показана высокая точность и чувствительность метода. Ранее дендрограммы сходства, использующие такую меру близости, либо не строились, либо строились, но использовались лишь для целей предварительной классификации.

Впервые введена и обоснована мера внутренней гетерогенности (МВГ) блока выравненных последовательностей. Полученная нами мера обладает рядом важных и интересных свойств, например, относительной независимостью от конкретной матрицы сходства символов.

Опираясь на эту меру, нами предложена двухкомпонентная модель представления одной позиции выравнивания. Показано, что результат множественного выравнивания аминокислотных последовательностей хорошо описывается этой двухкомпонентной моделью. Впервые получена оценка дисперсш! величины веса элемента дот-матрицы, опирающаяся только на МВГ, которая весьма точно приближает прямо посчитанную дисперсию.

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

Впервые получены асимптотические и аппроксимированы точные выражения для функции распределения (Мс) в зависимости от длины интервала, где осуществлялся его поиск. Эти точные выражения позволяют, по крайней мере, вдвое поднять точность вычисления статистической значимости наблюдаемого сходства.

Практическая ценность работы" состоит в следующем: а) Реализован алгоритм кластеризации последовательностей, который можно использовать и который уже активно используется в институте для решения различных биологических задач -от целей множественного выравнивания до оценки скоростей эволюции, б) предложен быстрый, точный и свободный от многих недостатков других методов алгоритм поиска аналогов заданной последовательности в базах данных.

Апробация работы. Результаты работы докладывались на 2 международной конференции по Биоинформатике, суперкомпьютерам и комплексному анализу генома, (StPetersburg Beach, Florida, USA, сентябрь 1992 г.), на Втором Сибирском Конгрессе по Прикладной и Индустриальной математике (Новосибирск, июнь 1996г.), а также на отчетных сессиях института Цитологии и Генетики 1993 и 1996г.

Пубяикятии -По теме диссертации опубликовано 4 статьи в рецензируемых изданиях и 5 тезисов докладов на Международных и Российских конференциях.

Структура работы. Работа состоит из следующих разделов: Определения часто используемых понятий. Введения, двух Глав, Заключения и Выводов. Работа изложена на 109 страницах и содержит 5 таблиц и 22 рисунка. Список литерату-

ры включает 100 ссылок.

Содержание работы.

Во введении обосновывается актуальность диссертационного исследования, формулируются его цата и задачи.

Глава 1 в первой своей части содержит обзор существующих в настоящее время методов классификации и сравнения последовательностей. Во второй части рассмотрены случаи использования олигопещдов (олишнуклеотидов) для установления схожести последовательностей биополимеров. Третья часть обзора литературы описывает все немногочисленные подходы к выяснению значимости наблюдаемого сходства последовательностей. В конце каждого раздела проводится обсуждение методов и разбор их достоинств и недостатков, как они представляются автору. В заключении работы делается краткий анализ полученных результатов и областей их применения.

Глава 2 посвящена описанию и обсуждению предлагаемых методов, демонстрации их применения и сравнению с альтернативными подходами, когда они существуют.

В первом разделе этой главы описан метод кластеризации последовательностей в процессе множественного выравнивания, обсуждены еш преимущества и недостатки, определена область применения и приведены примеры его успешного использования.

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

Для работы метода необходимы: а) Некоторый алгоритм, позволяющий осуществлять парные выравнивания последовательностей не единичной мощности, и б) Некоторая мера, позволяющая сравнивать выравнивания с различной мощностью.

Первое требование - наличие алгоритма парного выравнивания - не является новым. Второе требование (мера для взвешивания и сравнения между собой выравниваний различной мощности) - абсолютно новое. Мы полагаем, что именно невозможность непосредственного сравнения выравниваний различной мощности и есть та причина, из-за которой, подобный алгоритм до сих пор не появился. Заметим, что в литературе нет даже упоминаний о самой возможности такого подхода.

В конкретной реализации как алгоритм выравнивания выступал метод, разработанный автором с сотрудниками (Селедцов и др. 1995), мера сравнения описана в далее. Следует помнить, что чем более качественный алгоритм выравнивания и чем более адекватная мера будут использованы, тем лучшее множественное выравнивание и дендрограмму сходства молено будет ожидать. Далее подразумевается, что мера сравнения полученных выравниваний всегда дает "правильный" резуль-

тат. Это, как правило, невозможно, поскольку не известно в точности, что такое хорошее выравнивание и что есть большая степень похожести последовательностей. Однако такое допущение позволит белее ясно выразить особенности и преимущества предлагаемого нами подхода, избавляя от необходимости обсуждать неточности меры сравнения, в равной степени присущие всей без исключения методам кластеризации и множественного выравнивания.

Изложение алгоритма. 1) Пусть имеется выборка из N последовательностей, для которых требуется построить девдрограмму сходства. Для этого все пары последовательностей выравниваются, и результат сравнения (с использованием вышеупомянутой меры) заносится в матрицу В размерности NxN.

2) Далее выбирается наибольший элемент матрицы. Соответствующее этому элементу парное выравнивание рассматривается далее как самостоятельный, цельный объект, иначе говоря, как последовательность мощности 2.

Эти два шага предлагаемого алгоритма ничем не отличаются от таковых у других алгоритмов. Следующий же шаг наиболее сильно отличает его от всех других. Чтобы наиболее ясно понять это отличие и вытекающие отсюда последствия, кратко напомним, как обычно далее поступают другие методы. Каким-либо матричным методом, используя матрицу В, восстанавливается девдрограмма сходства, и затем все последовательности выравниваются в порядке, задаваемом девдрограм-мой. При нашем же подходе мы до самого последнего шага не знаем вида девдро-граммы кластеризации, нам известны лишь какие-то ее части.

3) Следующим шагом алгоритма является выравнивание этой, вновь полученной последовательности не единичной мощности со всеми остальными N-2 последовательностями, и занесение соответствующих весов сравнений в матрицу В. В результате на каждом шаге кластеризации число последовательностей уменьшается на 1. После этого мы имеем те же условия, с которыми начинали выполнение пункта 2), с тем лишь различием, что последовательностей стало на одну меньше.

Далее переходим к пункту 2), и делаем это до тех пор, пока у нас не останется только одна последовательность мощности N. Нетрудно понять, что эта последовательность и есть результат множественного выравнивания, а сам порядок, в котором осуществлялась кластеризация, представляет собой требуемую девдрограмму.

Чтобы понять отличия и преимущества предлагаемого подхода, рассмотрим на простом примере что происходит в дальнейшем с матрицей парных сравнений при: 1) использовании традиционных методов и 2) использовании предлагаемого нами метода.

Пусть кластеризуются/выравниваются четыре последовательности (А,В.СО), и нам известна правильная девдрограмма кластеризации ((ВС)А)1). Пусть парное выравнивание последовательностей А и В, осуществлено правильно в том смысле что это действительно наилучшее со всех точек зрения выравнивание, которое можно получить имея только эти последовательности. Но это выравнивание "не-

5

I

правильно" при рассмотрении всех четырех последовательностей. Пусть матрица тарных сравнений, такая как приведено в таблице 1.

Стандартный подход. Ппервыми будут объединяться последовательности С и В. Далее любой стандартный алгоритм пересчитывает матрицу. Пусть для определенности в этом качестве используется алгоритм иТОМА. Тоща новая матрица будет выглядеть так, как это отображено в таблице 2. Сравнение А с О не изменилось, а сравнение ВС с А и ВС с О вычисляется как среднее арифметическое соответствующих парных сравнений. Использование другого метода кластеризации не изменяет резу&тат принципиально, так как б любом случае результат сравнения обобщенной последовательности ВС с последовательностью А будет некоторой функцией от элементов матрицы парных сравнений.

В нашем примере, однако, известно, что выравнивание последовательностей Аи В, осуществлено "неправильно", и сходство последовательности А с уже выравненной обобщенной последовательностью ВС, уже не может быть никаким образом получено из матрицы парных сравнений последовательностей, так как мы теперь уже имеем дело с совершенно другим выравниванием. Следуя стандартной методике следующей объединяемой парой будет АО, что ошибочно.

Предлагаемый подход. Чтобы определить правильную величину сравнения обобщенной последовательности ВС с последовательностями А и О, необходимо взвесил, соответствующие выравнивая. Поскольку известно что множественное выравнивание, как правило, более однозначно и правильно чем парное, то можно ожидал, что в выравнивании обобщенной последовательности ВС с последовательностью А, подвыравнивание АВ окажется более правильным чем собственно парное выравнивание АЗ (Последовательность С,правильно выравненная как с В, так и с А, как бы- "держит" их) В свете вышеизложенного можно ожидать, что вес выравнивания обобщенной последовательности ВС с последовательностью А окажется больше чем полусумма парных сравнений, А с С и А с В. Пусть в этом случае матрица парных сравнений выгладит так, как показано в таблице 3. Сравнив ее с предыдущей можно видеть, что следующими объединяемыми вершинами будут ((ВС)А), а ке АО. То есть, используя предлагаемый подход и пользуясь вполне правдоподобными рассуждениями, мы получили иную и в нашем случае более правильную девдрограмму кластеризации, которая в свою очередь должна приводить к более правильному результирующему множественному выравниванию.

В заключение в конце раздела приведены примеры использования метода для решения Зх сильно различающихся нетривиальных задач. 1) Последовательности очень сильно гомологичны по всей дайне. Задача: определение порядка ветвления представителей, т.е. задача кладистики. 2) Умеренно гомологичные последовательности с неравномерным уровнем гомологии, присутствует как эволюционная, так и структурно - функциональная близость. Задача: провести их полную эволюцион-

А В С

13

50 64

40 24 32

Таблица 1.

А ВС

В с 32

¡> 40 28

Габлица.2.

А ВС

ВС 44

0 40 23

Таблица 3.

ную и структурно - функциональную классификацию, выявить участки имеющие важную структурно - функциональную роль. 3) Эволюционные отношения между сравниваемыми последовательностями не ясны или столь слабы, что могут считаться отсутствующими. Известна их некоторая общая функция. Задача: по возможности разбить последовательности на какие-то группы и, главное, выявить участки последовательностей, имеющих важную структурно - функциональную роль.

Как представители первой группы выступали гены 5S РНК удаленных организмов,-эти последовательности легко и, в общем правильно, выравниваются почти всеми методами выравнивания, но восстановление правильного порядка ветвления представляет довольно трудную задачу. Матричные методы совершенно не справляются с ней, а очень сложные алгоритмы, использующие принцип парсимо-нии, дают приблизительно такой же, как у нас, результат.

Вторую группу представляли 20 глобиновых белков. Выравнивание и построение децдрограммы для такой группы последовательностей является своеобразным экзаменом, для метода множественного выравнивания.

В качестве третьего примера была использована выборка ГТФ-связываюндах белков. Выборка состоит из трех не родственных между собой групп: а) мембранные сигнал-передаюшие G-белки эукариот; б) факторы атонгации про- и эукгри-от; в) RAS и RAS-подобные белки. Для данной выборки более интересна не ден-дрограмма, а само полученное множественное выравнивание. На всех трех выборках предлагаемый метод показал хорошие результаты и решил поставленные задачи. Для примера на рисунке 1 приведена девдрограма кластеризации 20 аминокислотных последовательностей глобинов.

В конце раздела приведено прямое сравнение предлагаемого метода с лучшими мировыми алгоритмами методом, предложенным МакКлур и сотр. (McClure et al., ¡994). Из рисунка 2 видно что наш метод , занимает первое - второе место. Отметим, .что результаты алгоритма DFALIGN, сильно завышены за счет использования априорной информации при множественной выравнивании.

Все вышеперечисленное позволяет сделать вывод, что предложен метод кластеризации последовательностей весьма эффективен и имеет широкий интервал приложения: от получения филогенетических деревьев до выявления функционально важных участков в белках. Методу не требуется никакая предварительная информация о последовательностях, а скорость его работы высока. Так, построение последней дендро-

ГВЮГПОБИН ХЕНОПИШН I

тмгвюптаин татвюглоБин

■ИОГПОЕИН «ЮГЛОБИН «ЮГЛОБИН «ЮГЛОБИН СГПОБИН ГЕЛОГЛОБИН ГЕМОГЛОБИН ГЕПОГЛОБЖ

„гаюглоем

0 ГЕЛОГЛОБИН

агпюгяокин таю то вин

ГЕЛОГЛОБИН

гелоглобш а плоти бж

ГЕЛОГЛОБИН

VITRECSCIUA SP......

POMSPOflIA AflOERSONII

i лтм...............

i вайи...............

ЧЕРЕПЙХИ.............

мллтм.............

массы«.............

ЦЕЛЫМИ.............

ЧЕЛОВЕКА.............

пяпшн..............

кгокатля............

ЧЕЛОВЕКА.............

UUY1EKKA.............

ОПОССУГИ.............

ляпши..............

КРОКОДИЛА............

стрдася..............

КЕНГУРУ..............

тлям...............

ЧЕЛОВЕКА.............

г

Рисунок 1. Дендрограииа 20 последовательностей глобинов.

р

г

DfALIW, г CL VSTÁL V

eALtTR£

граммы заняло только 4 минуты на процессоре I486DX-80.

oOFAIGN ■ АЬМ.1

□ CLUSTAL V

ле главы описан быстрый метод восстановления девдрограм-мы сходства последовательностей, • основанный на близости их ¿-плетного состава. Ь-гшетом далее будем назавать фрагмент последовательности

Во втором разде-

GL

КН

PRO

BNH

Рисунок 2. Сравнение качества множественных выравниваний, полученных разными алгоритмами на 4 выборках аминокислотных последовательностей. АЬГГОЕ - предлагаемый нами алгоритм. Высота столбиков соответствует проценту "правильно" выравненных остатков в соответствующей выборке.

определенного состава и порядка символов. Предлагаемый метод имеет самостоятельный интерес как метод позволяющий быстро классифицировать последовательности, без их предварительного выравнивания. Кроме того, он способен справляться со случаями крайне низкого сходства. В настоящей работе, однако главной его целью является подтверждение ранее описанного метода одновременного построения децдрограммы сходства и множественного выравнивания последовательностей. Действительно, этот метод в точности такой же, как и ранее, за тем лишь исключением, что вместо выравнивания и взвешивания результата производится оценка близости £-гиетного состава последовательностей. Если и в этом случае метод будет давать хорошие результаты, можно будет с большей уверенностью говорить, что используемые нами в обоих случаях подход правилен.

Оптимальная длина ¿-плета определялась, исходя из предположения что при равных частотах использования символов /^плеты такой длины должны встречаться в случайных последовательностях с частотой меньше единицы, т.е.

.р - L)<1 , где Lp средняя длина сравниваемых последовательно-

стей, N- количество последовательностей , Nabe количество символов используемого алфавита.

Когда установлено значение L , опишем собственно метод восстановления топологии децпрохраммы сходства. Все последовательности далее обозначаются как OTE (операционно-таксономнческие единицы). Частота определенного L-плета в OTE определяется как число копий данного L-плета во всех последовательностях, входящих в данную OTE, деленное на суммарную длину этих последовательностей. Частота ¿-го L-плета в j'-ой OTE обозначается как К{, а общее число рассматриваемых L-плетов, G, тоща можно определить некоторую меру, отражающую близость JL-плетного состава двух последовательностей. Мы сравнивали д ве таких меры, определяющих степень близости/-ой и т-той OTE:

1=1v ' i—1

первая мера представляет собой квадрат евклидова расстояния, а вторая отражает степень коррелированное™ частот JL-плета в сравниваемых OTE. Вторая мера показала устойчиво хорошие результаты в широком интервале значений L, от 3 до 12, и именно ее мы использовали в своей дальнейшей работе. Отметим что обычно используют более плохую евклидову меру.

Объединение OTE; слияние двух OTE осуществлялось двумя способами. Простой способ: Длина образованной OTE приравнивались сумме длин образующих ее родительских OTE, то же проделывалось для числа встреченных L-плетов, а затем вычу .... гсь частоты L-гаетов описанным выше способом. При сложном способе пр • лсь те же действия с тем лишь исключением, что частоты L-плетов, встречающихся лишь в одной OTE, уменьшались на следующий коэффициент

который отражал вероятность их наличия в передковой последовательности. Здесь N - общее число OTE, Nt - количество последовательностей в группе, ще ¿-плет не присутствует, N2 - количество последовательностей в другой группе, I - номер сияния. А - эмпирический множитель равный 2.5.

Собственно реконструкция децдрограмиы проводилась так: Все начальные OTE сравнивались с использованием указанной ранее меры, и результаты сравнений заполняли матрицу В. Затем из матрицы отбирался наибольший элемент. Соответствующие этому элементу OTE объединялись. В матрицу парных сравнений заносились пересчитанные заново результаты сравнений новой OTE со всеми оставшимися. Как и ранее, размер матрицы уменьшался на 1. Все делалось так же, как и ранее за тем исключением, что вместо выравнивания проводилось объединение, а сравнение последовательностей проводилось с использованием меры, основанной на встречаемости L-плетов. Как и ранее, порядок кластеризации определял получаемую децдрограмму.

Для проверки предложенного нами подхода была использована выборка 10 последовательностей 5S РНК, выборка аминокислотных последовательностей 20 глобиновых генов, представители обеих выборок принадлежали удаленным друг от друга таксонами, и выборка 87 последовательностей гаобиновых генов,самых различных организмов функционирующих на разных стадиях онтогенеза. Для всех этих выборок получены качественные дендрограммы, для выборки 87 глобинов, кроме того, подтвержден феномен молекулярной рекапитуляции.

Анализ реконструированных девдротрамм сходства показывает, что метод не уступает наиболее мощным алгоритмам, основанным на принципе парсимонии. Интересно отметить, что наиболее простой подход к построению дендрограммы в рамках предложенного принципа - применение метода UPGMA к матрице парного сходства последовательностей (что шесте с использованием евклидова расстоя-

(1)

ния и небольшой длиной Ь-плета постоянно используется) не дает хорошего результата ни на одной из проверяемых выборок.

В третьем разделе главы предлагается новый подход к проблеме учета неоднородности позиций множественного выравнивания, основанный на введении меры однородности в явном ввде. В отличие от метода, Вгсхкку а ей. (1993), который требует сложных расчетов при анализе каждого фрагмента выравнивания, наш метод позволяет оценить дисперсию веса целиком для данной пары последовательностей. Полученные результаты использованы в последних версиях программы, выполняющей множественное выравнивание (Селедцов и др. /995).

Рассмотрим пару обобщенных последовательностей а и Ъ, заданных в некотором алфавите длиной N. Каждая из этих последовательностей состоит из па и пь выравненных индивидуальных последовательностей (тоща в ¿-той позиции у той последовательности, составляющей обобщенную последовательность а, находится символ а/.у). Сходство символов алфавита описывает матрица в; элемент матрицы Би задает меру сходства (вес) пары символов с номерами х и у.

Рассмотрим фрагмент выравнивания последовательностей а и Ь, начинающийся в позициях * и у, соответственно, и имеющий длину I. Вес такого фрагмента выравнивания определяется по формуле (3):

ГСс = — П1 (2), Щу = ^х+к,у+к (3)

ПаМ ,=1у=1 *=0

Если известна функция распределения веса фрагмента выравнивания единичной длины (будем обозначать ее первый момент этого распределения ЛЛ, второй центральный момент - О1), то можно получить распределение веса фрагмента выравнивания длиной I путей /-кратной свертки Рф. В соответствии с центральной предельной теоремой распределение величины - ШЦIV®1 с ростом I стремится к нормальному с мат. ожиданием 0 и дисперсией 1.

Если заданы частоты символов в генеральной совокупности /¡, легко найти математическое ожидание и дисперсию веса случайной пары аминокислот:

ЛГ = £ %5к,т/к/т,(4) О = £ £(&„,* -М)2/»./*• С5)

*=1т=1 к=1т=1

Полезной статистической характеристикой алфавита является мат. ожидание веса для заданного символа к, -Ми (взвешенное среднее строки матрицы 5). Определим также некоторую величину, которую мы в дальнейшем будем называть "матричной ковариацией" С:

Мк = ; (6) с= ££ - - м)ль/к (7)

¿=1 /=1у=и=1

Легко вцдеть, что при выравнивании пары множественных последовательностей (и, > 1 и/или пь > 1) мат. ожидание - 1М1) / л/щГ равно 0. Рассматривая дисперсию прежде всего отметим два предельных случая: а) Позиции последовательностей а и Ь составлены из па и пь одинаковых символов (каждый столбец символов, последовательности, полностью вырожден); Ь)

Позиции последовательностей а и Ь состоят из па и пь разных символов (каждый столбец символов, соответствующий определенной позиции последовательности, представляет собой набор независимых случайных символов). .

Очевидно, что, поскольку в случае а) в формуле (2) под знаком суммы находится константа, дисперсия Wt r равна D. В случае Ь) происходит суммирование па х пь коррелированных случайных величин с известной дисперсией D и кова-риацией С. Несложные преобразования приводят к формуле:

Dl _ Р + (Пд +ПЬ ~1)С ф)

ПаПЪ

Это выражение аналогично формуле, приведенной Brodsky et al. (1993), с точностью до различий в определении веса фрагмента.

Позиции реальных выравниваний представляют собой набор символов, промежуточный по своим характеристикам между случаями а) и Ь). Обычно, такие столбцы представлены набором символов со сходными свойствами. Очевидно, что в этом случае X?1 будет меныпе, чем в случае а) (столбец неоднороден), но больше, чем в случае Ь) (символы не независимы). Для исследования такого случая необходима, во-первых, удобная для расчетов модель столбца выравнивания, и во-вторых, мера его однородности (от такой меры требуется, чтобы в случае а) она бьиа равна 1, а в случае Ь) - 0).

Рассмотрим i-тую позицию последовательности а. Вес некоторого произвольного символа с номером & на эту позицию равен Vi (10). Существует символ z, такой, что

V: = max(Vít), (9) ще Vk = — £soí j,k. <10>

к Па j=i (

Можно сказать, что г есть символ, "наиболее похожий" на данную позицию последовательности а. Тогда данную позицию можно описать как cuta (гае О < а £ 1) символов г и (1 - а)ла "усредненных" символов. Значение параметра а, которое наилучшим образом отражает предсгашеность символа z в данной позиции, равно:

Vz -Мг

а=ЙГяГ- О»

К недостаткам этой формулы относится то, что в редких случаях (при очень гетерогенных столбцах) Vz получается меньше Мг, что приводит к а < 0.

Выясним, насколько точно представление столбца выравнивания как апа символов z и (1 - а)лд "усредненных" символов соответствует реальности. Вес к-того символа на моделированную позицию будет равен:

Vjt^aSa+U-aW* . Нетрудно видеть, что рассмотренная выше мера (11) гарантирует равенство Vz = Vj'. Вовлекая в рассмотрение прочие символы алфавита, представляется естественным требовать, чтобы вес любого символа на моделированную позицию как можно меньше отличался от веса символа на реальную позицию. Средний квадрат ошибки веса будет равен

я2= ^-у*1)2/*. (13)

*=1

Подсташяя (12) в (13) и раскрыв скобки, и обозначив

Оз = 81,к-Мк,Оу = Ук-Мк,31= = =

*=1 *=1 получим выражение, эквивалентное (13):

£2 =а251-2о52 +53. (14)

Для нахождения минимума ошибки найдем экстремум этой функции, дифференцируя ее по а. При этом

а = Зг/Л и Ютт = 8з-о£г- (15)

Таким образом, выражение (15) дает оптимальное в смысле сформулированного выше требования значение а.

Пусть мера однородности данной позиции последовательности а есть а, а последовательности Ъ - р. Можно сказать, что данная позиция последовательности а содержит ра - оша штук некоторого ("характерного") символа и да = (1 - а)па штук случайных символов. Аналогично определяются значения рь и дь для последовательности Ь. Используя основные свойства дисперсии и ковариации, можно показать, что дисперсия веса данного элемента выравнивания: П1 _ РаРЬР + (.РаОь+ГЬОа)С ПАч Ра = р1 + Яа ^ (^ иЛ & = дЛ2Ра + 9а-1)

{РЬ и Оь аналогачно).

Для каждой позиции последовательностей в и 6 можно вычислить значение введенной нами меры однородности, получив, распределения этих величин. Обозначим функции платности этих распределений ш(а) и иь(Р). Тогда дисперсия любого фрагмента выравнивания единичной длины равна:

№ = (17)

оо

Как отмечалось ранее величина У^ЦУУ^ - 1М1) / л/Ш1 может служить оценкой статистической значимости веса фрагмента выращивания.

Для того чтобы выяснить, как наша оценка 2)1 описывает дисперсию веса фрагмента множественного выравнивания, мы сравнили ее с другими оценками и с прямо подсчитанной величиной дисперсии при выравнивании различных выборок. Результаты сравнения приведены на рисунке 3. Можно видеть, что предлагаемая нами оценка наиболее точно приближает реальное значение.

В четвертой часто главы предлагается точная и быстрая оценка достоверности наблюдаемого сходства выравненных последовательностей, необходимая при поиске сходства в базах данных и в приложениях филогенетического анализа. На сегодняшний день эту задачу нельзя считать удовлетворительно решенной. Имеется рад работ, в которых оценивается статистическая значимость сходства фрагментов выравнивания. Эти оценки требуют выполнения ряда жестких условий, в частности, - требования приблизительного равенства длин последовательностей и

требования отрицательности мат. ожидания элементов матрицы сходства символов. Нами предложен метод оценки статистической значимости фрагмента, обладающего максимальным весом при множественном выравнивании последовательностей, свободный от этих ограничений.

В дальнейшем будем считать, что матрица Я преобразована таким образом:

Рисунок 3. Дисперсия величины веса фрагмента выравнивания, пос-читаная при выравнивании различиях выборок (подписи снизу). Г{-прямо подсчотаная диспесия; и - в предположении о независимых символах; А - оценка по формулам (17,16,15); I - в предположении о полностью вырожденных стшбцах.__

S =

S-'ifpiPjSijrl/VDÍ, (18)

так что математическое ожидание (формула 2) становится равным 0, а дисперсия 1. При всех возможных координатах ж и у и последовательностях a и Ь, имеющих определенный характер неоднородности, можно определить функцию распределения величины Wx,y, в дальнейшем обозначаемую как Fs.

Рассмотрим фрагмент выравнивания, имеющий максимальный вес среди весов всех фрагментов дот-матрицы. Вес такого фрагмента, Wmw может служить мерой сходства сравниваемых последовательностей. Для случайных последовательностей Wmw представляет собой случайную величину с некоторой функцией распределения Fmw. Очевидно, что Fmw зависит как от функции Fs, так и от длин последовательностей. Рассмотрим вес поддиагонали дот-матрицы, максимальный для данной диагонали длины L, Wm. Введем функцию распределения этой величины - Fm- Очевидно, что вся дот-матрица, образованная последовательностями с длинами /а и 1ь (будем считать, что h ^ 1ь), может бьгть представлена как совокупность из la -1ь +1 диагоналей длиной 1ь и 2 х (Í& -1) диагоналей с длинами от 1 до 1ь -1. Тоща вероятность того, что максимальная на данной дот-матрице поддиагональ имеет величину Wm»<t (что есть искомая функция Fmw), определяется условием: Wm1 < t и W„2 < t и ... , где Li, Li, ... - длины всех диагоналей, образующих дот-матрицу. Это соответствует произведению функций распределения Fm (/), Fm2(О, - при условии независимости соответствующих им случайных величин.

Fmw{t) = (FjLb{t)f'lb+1 *('JÍ FÁ(í)j ■

Таким образом, остатся определить вцд функции Fm, и можно считать поставленную задачу решенной. После проведения ряда численных экспериментов было установлено, что вид функции Fj¡¡(t) не зависит от Fs , и в дальнейшем мы считали Fs функцией нормального распределения со средним 0 и дисперсией 1.

(19)

Ниже мы приводим такие выражения для верхнего Т Т(() и нижнего Т -I (<) граничных значений функции 1 - . что истинно двустороннее неравенство ТТСО £ 1- /#(») 2: т 1«), Доказано, что

Tl « j или

20-1(2/2

-■ш

(20), a rt = 2-

\7l

- е

(21)

1 - 2<р(е)

где w(x) = f—j==-du, эти выражения справедливы для любых е>0. ; -J2-K

Мы получили граничные функции для 1 - Fjk(t). Можно видеть, что как верхняя, так и нижняя граничная функция при больших значениях аргумента

г- ехр(-(ах - Ь)2 (х > 3ыЬ) имеют одну и ту же аналитическую форму F*(x) = С—----,

где коэффициенты С, а и b могут иметь (а могут и не иметь) некоторую зависимость от L. Соответствешю сама функция F,k(x может бьггь записана либо как 1 - F* (х либо (при F*(x)<< 0.01) как exp(-F*(x)). Из этого непосредственно следует, что -ln(-ln(F,£(f))) должен представлять собой квадратичную кривую вида <2 + In(i) + S- На рисунке 4 показано соответствие этих функций.

Поскольку полученные результаты дают граничные значения величины функции F„'i(x и, как следствие,- общий характер ее поведения, нам остается лишь получить удовлетворительные приближения этой функции, основываясь на полученном общем виде ее формы. Для этого проводилось численное моделирование и построение функций распределения дня различных значений L. Для аппроксимации нами была выбрана функция вида exp(-F*(*)).

До длины L строились ряды нормально распределенной величины со средним 0 и дисперсией 1. В этом раду находился фрагмент с максимальной суммой элементов (©). Функция распределения величины © строилась многократным повторением этой процедуры. Мы проводили моделирование для следующего набора длин диагоналей (L): 10, 30, 60, 80, 120, 150, 180, 300, 400, 750, 1000, 2000. Для каждой длины было проведено от 8 до 10 миллионов опытов; в последующем отдельно для длин 80 и 120 было проведено примерно еще по 300 миллионов опытов для сравнения аппроксимированной (Fj-) и реальной (/$) функций распределения в далекой положительной области аргумента.

Рисунок 4. Аппроксимация двойного логарифма функции распределения квадратичной кри вой. Можно видеть •по две эти кривые практически не различаются.

Нами было установлено, что -1п(-1п((^)) действительно представляет собой функцию вцца: х2 / 2 + 1п дг + С, где х = -А/ + В, что полностью согласуется с результатами полученными в предыдущем разделе (рисунок 4). Далее для каждого исследуемого значения длины £ были подобраны коэффициенты А, В и С, и исследована зависимость коэффициентов А, В и С от длины диагонали (Ь). При фиксированном значении С иэдостаточно широкого диапазона, зависимость А и В от длины фрагмента в двойных логарифмических координатах представляет собой прямую (1пА = Аа 1п£ + Ва\ 1пВ = Аь 1пЬ + Вь). Получены значения коэффициентов линейной зависимости Из рисунка 5 можно ввдеть, что полученная на основе аппроксимированных (а не подобранных) коэффициентов А и В функция хорошо приближает функцию распределения при достаточно больших значениях аргумента. Рисунок показывает соответствие величин 1п(1 — Ра) и 1п(1 -РЦ{). Видно, что кривые практически не различаются при больших значениях аргумента, а при не очень больших значениях аргумента различия крайне незначительны.

Кратко перечислим, какие новые результаты были получены и в чем состоит их ценность. Впервые получено асимптотическое решение для функции распределения величины веса фрагмента выравнивания максимального веса для случая Е{Ц'х,у} = 0, (формула (21)). В литературе имеется решение такой задачи только для случая Е ПКг.^} < 0. Получены точные (не асимптотические) выражения для этой функции распределения на диагоналях произвольной длины. Это позволяет, используя формулу (19), получить точные значения вероятности наблюдать фрагмент заданного веса при выравнивании последовательностей с действительно произвольными длинами. Напомним, что известный до настоящего времени подход позволял работать только с последовательностями примерно равной, и лучше - большой дайны. Это очень важное отличие, оно позволяет эффективно использовать наш подход для поиска сходства в базах данных.

Выводы.

1. Разработан новый высокоэффективный алгоритм построения девдрограммы сходства последовательностей биополимеров. Алгоритм свободен от многих недостатков предшествующих методов и может бьггь использован для обработки самых различных по степени схожести последовательностей. Реализующая алгоритм программа может использоваться для решения широкого класса научных задач, от построения филогенетических деревьев до выявления структурно/функционально важных областей в последовательностях РНК, ДНК и белков.

2. Показана возможность сравнения между собой оценок качества выравниваний, образованных последовательностями различной мощности.

3. Предложена новая схема кластеризации и множественного выравнивания, расширяющая и обобщающая существующую методику прогрессивного выравнивания.

25 чти

2>

15

10

5

-23 У , I_,» 33 40 Ю

Рисунок 5. Соответствие эмпирической и аппроксимированной функций распределения.

4. Разработан алгоритм построения девдрограмм сходства последовательностей на основе частот встречаемости олигонуклеотвдов или олигопетвдов (£,-плетов) Показана высокая точность и чувствительность метода. Определены границы его применения.

5. Введена и математически обоснована мера внутренней гетерогенности блока выравненных последовательностей. На основании этой меры предложена двух-компонентная модель представления одной позиции выравнивания. Получена оценка дисперсии величины веса элемента дот-матрицы, опирающаяся только на степень внутренней гетерогенности последовательностей. Полученная оценка весьма точно приближает прямо подсчитанную дисперсию.

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

7. Получены верхние и нижние асимптотические границы функции распределения величины максимального веса фрагмента выравнивания. Аппроксимированы точные выражения для функции распределения величины максимального веса фрагмента выравнивания. Определены пределы приложения полученных статистических оценок.

Пуйтпсдщш. Основное содержание диссертации предстазлено в работах:

1. Соловьев В.В., Селедцов И.А. Реконструкция филогенетических деревьев на основе анализа относительно консервативных участков нуклеотидных или аминокислотных последовательностей. II Докл. Акад. Наук СССР. 1991. Т.321. Сф.1109-1117.

2. Селедцов И.А., Вульф Ю.И., Макарова К.С., Множественное выравнивание последовательностей биополимеров, основанное на поиске статистически значимых общих участков. // Малек. Биал. 1995. Т.29. С. 1023-1039.

3.Макарова К.С., Вульф Ю.И., Селедцов И.А., Ратнер В.А. Эволюция рет-рогранспозонов gypsy-rpynmi: филогенетический анализ доменов, входящих в состав POL-палипрогеина // Генетика. 1995. Т.31. Сгр.1614-1629.

4.Solovyev V.V., Seledtsov I.A., A new approach to the phylogenetic tree construction based on the relatively conservative regions of the nucleotide and amino acid sequences. // International Journal of Genome Research. 1993. V.l. P.177-185.

5.Solovyev V.V., Seledtsov I.A., Multiple alignment and Phylogenetic Tree construction of genetic macromolecules. // 2nd International Conference on Bioinformatics, Supercomputing and Complex Genome Analisys.1992. StPetersburg Beach. Florida. USA. P.117-120.

6.Селедцов И.А., Вульф Ю.И., Макарова K.C., Статистическая значимость фрагмента выравнивания - зависимость от однородности последовательностей. // Второй Сибирский Конгресс по Прикладной и Индустриальной Математике (ИНПРИМ-96), Новосибирск, 25-30 июня 1996г. / Тезисы докладов Т.1, Стр 35.

7.Вульф Ю.И., Селедцов И.А., Макарова К.С., Статистическая значимость фрагмента выравнивания - зависимость от длины последовательностей. // Второй Сибирский Конгресс по Прикладной и Индустриальной Математике (ИНПРИМ-96), Новосибирск, 25-30 июня 1996г. / Тезисы докладов Т.1, Стр 23.