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

Постановка задачи Множество геномов Таблица ортологов Сравнение белковых последовательностей Наборы областей перед ортологичными генами Регуляторные сигналы Программа поиска сигналов кластеризация Регулоны Геном 1 Геном 2 Геном 3 ген1 ген2 ген3 ген4 Ген1 CCCTTCAGACCGCAATACTAGACCGCAATACTGCGGGTTT CCATGTTATCGAGTAAGTTACCGCAAAAGCGGCATTGGAC CGACCGCAACTAGACCGCAATACTGCATACACCACCACAT Ген1 ACCGCAA ACCACAA ACCGCAA Ген2 ACCGTAA ACCGCAA ACAGTAA Ген3 TTCTGAG TACTGAG TACTCAG Ген4 TTCTGTG TACTGAG TACTCTG Ген1 ACCGCAA Ген1 ACCACAA Ген1 ACCGCAA Ген2 ACCGTAA Ген2 ACCGCAA Ген2 ACAGTAA Ген3 TTCTGAG Ген3 TACTGAG Ген3 TACTCAG Ген4 TTCTGTG Ген4 TACTGAG Ген4 TACTCTG регуляторАрегуляторВ Геном1ген1, ген2ген3, ген4 Геном2ген1, ген2ген3, ген4 Геном3ген1, ген2ген3, ген4 Ген2 CCCTTCAGACCGCAATACTAGACCGCAATACTGCGGGTTT CCATGTTATCGAGTAAGTTACCGCAAAAGCGGCATTGGAC CGACCGCAACTAGACCGCAATACTGCATACACCACCACAT Ген3 CCCTTCAGACCGCAATACTAGACCGCAATACTGCGGGTTT CCATGTTATCGAGTAAGTTACCGCAAAAGCGGCATTGGAC CGACCGCAACTAGACCGCAATACTGCATACACCACCACAT Ген4 CCCTTCAGACCGCAATACTAGACCGCAATACTGCGGGTTT CCATGTTATCGAGTAAGTTACCGCAAAAGCGGCATTGGAC CGACCGCAACTAGACCGCAATACTGCATACACCACCACAT

Классификация алгоритмов Статистические – определяют сигналы в кластеры в соответствии с апостериорным распределением вероятностей. Иерархические – структурируют исходные данные, сравнивая фрагменты попарно друг с другом и объединяя похожие.

Van Nimvegen et al., 2002 Разбиение C -- всегда добавляем сигнал в кластер -- добавляем сигнал в кластер с вероятностью

– распределение мотивов по кластерам Qin et al., 2003 Алгоритм BMC (Bayesian motif clustering) n – мотивов N – потенциальных кластеров – номер кластера, содержащего мотив i

где – частота встречаемости нуклеотида i в позиции k мотива, – среднее значение частоты в столбце k. Hughes et al., 2000 D

ClusterTree-RS D ATAATCG ACAATCG AGAAACC CTAATCG ACAATCG ATAATCG ACAATCG AGAAACC CTAATCG ACAATCG … где Ik – информационное содержание в позиции k для общего набора сайтов [9], fj(i, k) – частота встречаемости нуклеотида i в позиции k для набора сайтов дочернего узла j, – среднее значение частоты в столбце k

ClusterTree-RS … …… … R>0 R

ClusterTree-RS Определение кластера ATAATCG ACAATCG AGAAACC CTAATCG ACAATCG ATAATCG ACAATCG AGAAACC CTAATCG ACAATCG … tgca tgca tgca … =

ClusterTree-RS Определение кластера

Сравнение алгоритмов Таблица 1. Сравнение средних значений ошибки для различных существующих методов кластеризации. Размер сигнала Ошибка a KM b HC-1 c HC-2 d BMC-1 e BMC-2 f ClusterTree- RS g 2-4 сайтов Частота ошибок, % (E, σ) 32,9 (5,2)26,3 (6,1)63,7 (1,7)9,0 (1,7)5,8 (0,2)10,7 (2,0) Кол-во кластеров, (E, σ) (4,2)34,4 (1,5)38,0 (1,3)49,8 (2,2) 2-10 сайтов Частота ошибок, % (E, σ) 33,4 (3,9)14,1 (3,1)25,7 (2,4)3,3 (1,0)2,5 (0,1)5,7 (1.0) Кол-во кластеров, (E, σ) ,9 (6,7) 40,6 (1,2)41,6 (0.6)46,8 (1,7) 5-10 сайтов Частота ошибок, % (E, σ) 31,6 (4,6)3,9 (1,1)11,0 (1,5)2,6 (0,4)2,2 (0,0)3,6 (0,7) Кол-во кластеров, (E, σ) 43 66,0 (3,9)41,4 (0,7)42,0 (0,1)43.2 (1.0)

Достоинства и недостатки Иерархические – работают быстро, но менее надежны. Статистические – более гибкие, но работают долго.

Благодарности Миронову Андрею Александровичу Макееву Всеволоду Юрьевичу Гельфанду Михаилу Сергеевичу Калининой Ольге Вячеславовне