Поиск протяженных повторов в геномах на основе спектрально-аналитического метода Доклад Земледельцева Д.И. - презентация

1 Поиск протяженных повторов в геномах на основе спектрально-аналитического метода Доклад Земледельцева Д.И.

2 Введение Анализ последовательности ДНК, в том числе содержащихся в ней повторов, является одной из основных задач, решаемых биоинформатикой. Актуальность изучения повторов подкрепляется тем, что у человека до 50% ДНК приходится на повторы.

3 Типы повторов Разнесённые повторы обязаны появлением действию транспозонов. Они в данной работе подробно не рассматриваются. Тандемные повторы являются результатом дублирования фрагментов ДНК, когда копия фрагмента следует сразу за образцом.

4 Тандемные повторы Внутри себя она делятся на четыре класса по протяжённости: 1)Микросателлиты – до 6 н.п. 2)Минисателлиты – н.п. 3)Саттелитная ДНК – н.п. 4)Мегасателлиты – свыше 1000 н.п.

5 Роль Совсем недавно повторы представлялись как «мусорная» («эгоистичная») ДНК безо всякой функции. В 2004 году впервые были получены подтверждения гипотезы о связи тандемных повторов и морфологической вариабельностью видов. У млекопитающих, как предполагается, они связаны с т.н. «цис- регуляторными районами», влияющими на экспрессию генов.

6 Предполагаемый механизм работы Количество повторов паттерна в участках мегасателлитов оказалось индивидуально. Их роль состоит в том, чтобы обеспечить такую укладку эухроматина, чтобы транскрибируемая ДНК сформировала специфический паттерн экспрессии.

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

8 Классические вычислительные методы На данный момент разработано множество алгоритмов и программ для вычислительной оценки подобия фрагментов ДНК и её производных (белков, РНК). Большинство алгоритмов основаны на базовых принципах обработки текстовой информации, таких как расстояние Хэмминга или редакционное расстояние Левенштейна.

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

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

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

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

13 Основные этапы 1) Представление нуклеотидной последовательности в виде набора функций-аналогов. 2) Преобразование функций-аналогов в спектральное представление. 3) Сравнение спектров разложения. 4) Отображение и анализ матрицы спектральной гомологии.

14 Расчет функции-аналога последовательности ДНК Разбиение алфавита A = {A,T,G,C} на два подмножества A1 и A2, так что A1 A2 = A: 1, если si A1 gA1(si) = 0, если si не A1 В качестве A1 мы можем взять его подмножество {G,C}.

15 Расчет функции-аналога последовательности ДНК Функция аналог представляет собой сумму gA1(si) при продвижении окна длиной W1 c шагом d1. Она получается считающей, то есть при каждой встрече в последовательности G или C она увеличивается на единицу.

16 Расчет функции-аналога последовательности ДНК Для обеспечения однозначного декодирования нуклеотидной последовательности из функции-аналога необходимо, чтобы d1 = 1, а количество линейно-независимых функций-аналогов должно быть две. При d1 не равным 1 теряется некоторая точность, но достигается ускорение времени счета при больших размерах обрабатываемых последовательностей за счёт прореживания.

17 Расчет функции-аналога последовательности ДНК Зная функцию-аналог fi, полученной при d1 = 1 и начальный фрагмент последовательности длиной W1 1 последовательность можно декодировать. Соотношение: f CT =W1 f GA можно использовать для оценивания комплементарных повторов.

18 Получение спектров разложения На данном этапе функцию f GC нужно разделить на фрагменты для преобразования в коэффициенты разложения по ортогональному базису. Для этого фиксируется окно W2, двигается по функции f GC с шагом d2, и на каждом шаге фрагмент, попавший в окно, преобразуется в коэффициенты разложения. Вектора коэффициентов разложения сохраняются для дальнейшей оценки близости между ними.

19 Выбор системы ортогональных полиномов Полином Лежандра непрерывного аргумента Полином Фурье непрерывного аргумента Полином Чебышёва дискретного аргумента

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

21 Базис Лежандра Представлен через формулу Родриге; z – комплексная переменная.

22 Базис Лежандра при вычислении коэффициентов разложения требуется интерполяция аппроксимируемой функции с постоянной сетки на неравномерную сетку узлов квадратурной формулы Гаусса, что приводит к дополнительным вычислениям.

23 Базис Чебышева Одна из формул представления в явном виде (решения уравнения Пелля в кольце многочленов с вещественными коэффициентами)

24 Базис Чебышева является дискретным аналогом базиса Лежандра и состоит из функций, ортогональных на равномерной сетке с единичным весом, поэтому процесс интерполяции можно исключить при вычислении коэффициентов разложения.

25 Базис Чебышева Однако известно, что вычисление полиномов Чебышева дискретного аргумента по рекуррентным формулам обладает неустойчивостью, что связано с отказом от интерполяции на сетку Гаусса. Кроме того, рекуррентное соотношение для полиномов Чебышева дискретного аргумента является более сложным по количеству вычислительных операций.

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

27 Базис тригонометрических полиномов Фурье В конечном итоге наиболее рациональное решение - использовать для представления функции в спектральном виде разложение по базису тригонометрических функций: B = {1\2, sinkx, cos kx,...}, k=1, 2, где k – номер гармоники. Система функций (фи)i(x) B, i= 0,1,..., удовлетворяет условию ортогональности в рамках скалярного произведения

28 Базис тригонометрических полиномов Фурье, определённого как определённый интеграл от минус пи до пи произведения фиi(х) и фиj(х) по dx, равный пи, если i = j, равный нулю, если i не равно j. Дискретный аналог на равномерной сетке из W2 узлов xk = пи\W2 (2k1W2) при k = 1,...,W2 является сумма от 1 до W2 с коэффициентом пи\W2.

29 Базис тригонометрических полиномов Фурье Особенностью базиса Фурье является то, что он предназначен для аппроксимации периодических сигналов, а фрагменты функций-аналогов последовательности не являются периодическими. Но поскольку в данной задаче используется оценка интегрального среднеквадратичного отклонения функций, то эффект Гиббса, который возникает при аппроксимации разрывных сигналов, имеет локальный характер (в данном случае проявляется на концах интервала) и практически не влияет на оценку интеграла отклонения функций.

30 Сравнение спектров разложения Для оценки близости двух фрагментов f и g используется метрика, согласованная с нормой и скалярным произведением: ро( f,g) = [[f g]] = sqrt( f g, f g). ( f g, f g) = сумма от 0 до L1 по (CkDk)^2(фиk,фиk), где Ck и Dk - коэффициенты разложения f и g соответственно.

31 Сравнение спектров разложения решающее правило основано на проверке следующего неравенства: тета( f,g) эпсилон, где эпсилон [0,1] пороговое значение решающего правила, L - количество коэффициентов разложения и тета( f,g) =1\2W1^2 суммы от 0 до L1 по (CkDk)2

32 Сравнение спектров разложения Среднеквадратичное отклонение является монотонно возрастающим по числу коэффициентов разложения, что позволяет прервать вычисление суммы квадратов, если пороговое значение e превышено.

33 Формулы для инвертированных повторов Для поиска участков с прямыми повторами векторы коэффициентов разложения сравниваются выбранной метрикой по формуле (12), а для того, чтобы из коэффициентов, отвечающих за прямое сходство, получить коэффициенты, которые будут соответствовать инвертированным повторам, требуются провести два типа преобразований над кривой содержания. Смысл первого преобразования сделать комплементарным один из сравниваемых фрагментов кривой к другому, а второе разворачивает этот фрагмент в противоположном направлении. Оба преобразования происходят в пространстве коэффициентов разложения.

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

35 Матрица спектральной гомологии Автоматический анализ матрицы спектральной гомологии позволяет выделить наиболее существенные участки сравнения. Для более точного определения координат повторов требуется этап верификации. Для того чтобы повысить качество распознавания, одновременно используются две кривые f GC и f GA, при этом ширина окнаW2 не меняется.

36 ПРИЛОЖЕНИЯ СПЕКТРАЛЬНОГО АЛГОРИТМА ПОИСКА ПОВТОРОВ

37 Поиск протяженных тандемных повторов В результате анализа Mus musculus и Rattus norvegicus, было выявлено некоторое количество протяженных повторов, тем не менее под искомый шаблон также попадали ранее известные многократно повторяющиеся сателлиты длиной порядка 300 п.н. Анализ 17-й хромосомы кролика выявил регион, в котором находятся протяженные тандемные повторы. Длина мотива приблизительно равняется 2623 н.п. Данный повтор был опубликован в RepBase под именем MSU1

38 Поиск протяженных тандемных повторов Копии повтора отличаются друг от друга минимально на 4.2%, максимально на 22.7%, в консенсусную последовательность входит 47%строго консервативных позиций. Для поиска повтора MSU1 были использованы следующие параметры: W1 = 2500,W2 = 10000,d2 = 2500,L = 15, эпсилон =

39 Поиск протяженных тандемных повторов При анализе 7 хромосомы Mus musculus найден кластер, состоящий из тандемных повторов длиной порядка 1873 н.п. и количеством копий более 130. Каждая копия содержит в себе ген SNORD115 протяженностью 89 н.п.

40 Полногеномное сравнение Логичным продолжением поиска мегасателлитных тандемных повторов стало полнохромосомное сравнение организмов Mus musculus и Rattus norvegicus. Построена генерализованная таблица подобия, полученная после полногеномного сравнения ДНК крысы и мыши. Отображены повторы длиной не менее 200 тысяч нуклеотидов. Такие повторы хорошо согласуются с известными районами синтении.

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

42 Сравнение с ДНК-гибридизацией Одним из интересных мест человеческой Y хромосомы является протяженный инвертированный повтор длиной порядка 300 тыс. н.п., повтор сильно разбит, между схожими участками имеются области, где сходство минимально или отсутствует. Повтор ограничивает область размером в 3.5 млн.н.п. и, вероятно, является причиной инверсии этой области.

43 Литература «Поиск протяженных повторов в геномах на основе спектрально-аналитического метода» Панкратов А.Н., Пятков М.И., Тетуев Р.К., Назипова Н.Н., Дедус Ф.Ф.; «Гены» под ред. Б. Льюина; «Основы высшей математики и её приложения к биологии» Ю.Н. Сударев, Т.В. Радославова, Т.В. Першикова; «Элементы теории функций и функционального анализа»,1976 А.Н. Колмогоров, С.В. Фомин; «Классические ортогональные полиномы дискретной переменной» Никифоров, Суслов, Уваров.

44 Благодарности Докладчик выражает огромную благодарность доц. каф. мат. анализа мехмата МГУ Александру Николаевичу Боброву и сотруднику Института молекулярной генетики РАН Алине Павловне Корбут за консультации.

45 Благодарю за внимание