Будем считать, что вместе с затравкой р задан и ее автомат B(р) = <QB, qB0, QFB , A, цB>. Такой автомат для всех известных классов затравок может быть построен на основе автомата Ахо-Корасик, специальная конструкция автомата для классификационных затравок представлена в п.4.3.4. Из результатов раздела 5.1 вытекают следующие утверждения.

Утверждение 5.2.1.Пусть A - алфавит выравниваний, G= <QG, q0G, A, сG > - конечно-автоматный генератор, задающий распределение вероятностей с на Am; р - затравка и B(р) = <QB, qB0, QFB , A, цB> - автомат затравки р. Тогда чувствительность Sens(р, m) затравки р относительно множества выравниваний Am может быть найдена методом динамического программирования за время O(|QG|2*|QB|*m*|A|) с использованием памяти O(|QG|*|QB|). Если автомат B(р) - детерминированный, то время работы равно O(|QG|*|QB|*m*|A|).

Следствие 1. Пусть распределение вероятностей на множестве Am - бернуллиевское. Тогда для времени и памяти вычисления чувствительности Sens(р, m) верны оценки TimeBern? O(|QB|*m *|A|) и SpaceBern? O(|QB|*m)

Следствие 2. Пусть распределение вероятностей на множестве Am - это Марковское распределение вероятностей с порядка r. Тогда для времени и памяти вычисления вероятности PG(L) верны оценки TimeMarkov? O(|QB|*m *|Ar+1|) и SpacMarkov? O(|QB|*m *|Ar|)

Утверждение 5.2.3.Пусть р - затравка в алфавите последовательностей П, A - алфавит выравниваний, согласованный с затравкой р и автомат B(р) = <QB, qB0, QFB , A, цB> является автоматом Ахо-Корасик. Пусть далее на множестве Am задано Марковское распределение вероятностей с порядка r. Тогда чувствительность Sens(р, m, с) затравки р относительно множества выравниваний Am и распределения с может быть найдена методом динамического программирования за время O((|QB|+|Ar|)*|A|*m) с использованием памяти O((|QB|+|Ar|)).

В разделе 5.3 приведен еще один пример приложения техники, описанной в разделе 5.1, - вычисление значимости найденного кластера регуляторных сайтов. Факторы регуляции транскрипции (ФРТ) связываются с фрагментами ДНК, содержащими специфичную для данного фактора последовательность нуклеотидов. Как правило, все последовательности, с которыми может связываться данный ФРТ имеют одну и туже длину. Множество таких последовательностей называется мотивом связывания ФРТ. В геноме область связывания ФРТ расположена перед регулируемым геном и называется цис-регуляторным модулем (ЦРМ). В последние годы было показано, что регуляция транскрипции с помощью ФРТ носит кумулятивный характер: в регуляции может участвовать несколько ФРТ, причем для каждого из них может быть несколько потенциальных мест связывания (вхождений соответствующих мотивов). Существующие программы распознавания ЦРМ основаны на поиске фрагментов генома, в котором перепредствлены соответствующие мотивы. Для практического использования этих программ необходимы средства оценки значимости полученных результатов. Формально задача может быть поставлена следующим образом.

Фиксируем алфавит ДНК Д={a, c, g, t}. Как и в разделе 5.2, будем считать, что на Am (здесь m - длина предполагаемого ЦРМ) есть распределение вероятностей с, которое задается конечно-автоматным генератором G= <QG, q0G, A, с G >. В частности, это распределение может быть Бернуллиевским или Марковским некоторого порядка r > 0.

Определение 5.3.1. Мотив длины t - это множество слов M Дt.

Определение 5.3.2. Пусть M - мотив длины t, D Дm - последовательность ДНК длины m; m ? t. Вхождение мотива M в последовательность D - это фрагмент D[x, x+t-1] такой, что D[x, x+t-1] M.

Пусть D[x1, x1+t1-1] - вхождение мотива M1 и D[x2, x2+t2-1] - вхождение мотива M2. Эти вхождения пересекаются, если пересекаются отрезки [x1, x1+t1-1] и D[x2, x2+t2-1].

Определение 5.3.2. Пусть дан набор M = < M1 , …, Ms >, состоящий из s мотивов Mi длины ti (i=1, …, s) и вектор k = < k1 , …, ks >, состоящий из s натуральных чисел ki (i=1, …, s). Пусть D Дm - последовательность ДНК длины m. Набор мотивов M имеет k -вхождение в последовательность D, если для каждого i {1, …, s} в D есть не менее ki (возможно, пересекающихся) вхождений мотива Mi..

Введем следующие обозначения:

F(M, k) - множество всех последовательностей из Д*, для которых существует k -вхождение набора M;

F(M, k, m) - множество всех последовательностей из Дm, для которых существует k -вхождение набора M;

В качестве меры достоверности потенциального ЦРМ длины m, содержащего ki вхождений мотива Mi (i=1, …, s) при заданном распределении вероятностей с на Дm используется величина Pс(F(M, k, m)), где M = < M1 , …, Ms > и k = < k1 , …, ks >. С помощью техники, описанной в п. 5.1, вычисление этой вероятности можно свести к вычислению обобщенной статистической суммы и, следовательно, найти искомую вероятность алгоритмом, основанным на методе динамического программирования.

Приведенные ниже утверждения дают оценки сложности этого алгоритма для различных вариантов задания распределения вероятностей с. Во всех этих оценках в качестве параметра фигурирует количество |QC| состояний автомата Ахо-Корасика C для множества М0 = М1… Мs. В цитированной выше работе Ахо и Корасик показано, что

|QC| ? L(M), (5.3.1)

где L(M) - суммарная длина всех слов из множества М0. В приведенных ниже утверждениях фигурирует величина |QC|, а не более естественная величина поскольку, как показано в разделе 4.3, оценка (5.3.1) недостаточно точна.

Утверждение 5.3.3. Пусть M = < M1 , …, Ms > - набор мотивов в алфавите A; k == < k1 , …, ks > - вектор с натуральными компонентами, С = <QC, q0C, QFC, A, цC> - автомат Ахо-Корасик для множества М0 = М1… Мs и G= <QG, q0G, A, сG > - конечно-автоматный генератор, задающий распределение вероятностей с на Am.

Тогда вероятность Pс(F(M, k, m)) множества F(M, k, m) относительно распределения с может быть найдена методом динамического программирования за время O((|QC|*k1 *… *ks*m*|QG|2*|A|) с использованием памяти O(|QC|*k1 *… *ks *|QG|). Если генератор G - детерминированный, то оценка времени может быть понижена до O((|QC|*k1 *… *ks*m*|QG|*|A|)

Следствие. Пусть распределение вероятностей на множестве Am - Бернуллиевское. Тогда для времени и памяти вычисления вероятности Pс(F(M, k, m)) верны оценки TimeBern? O((|QC|*k1 *… *ks*m*|A|) и SpaceBern? O(|QC|*k1 *… *ks ).

Утверждение 5.3.5. Пусть M = < M1 , …, Ms > - набор мотивов в алфавите A; k == < k1 , …, ks > - вектор с натуральными компонентами, С = <QC, q0C, QFC, A, цC> - автомат Ахо-Корасик для множества М0 = М1… Мs. и с - распределение вероятностей на Am, задаваемое марковской моделью порядка r.

Тогда вероятность Pс(F(M, k, m)) множества F(M, k, m) относительно распределения с может быть найдена методом динамического программирования за время O( (|QC|*k1 *… *ks+ |A|r) *m*|A|) с использованием памяти O(|QC|*k1 *… *ks+ |A|r)

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

1. На основе конечно-автоматного представления семейств последовательностей и конечно-автоматного описания вероятностных моделей предложен единый подход к вычислению вероятностей сигналов в случайных последовательностях и их выравниваниях. Разработаны методы построения затравок для поиска локальных сходств в нуклеотидных и аминокислотных последовательностях.

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

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

4. Предложен алгоритм предсказания внутренних петель при построении оптимальной вторичной структуры РНК с временной сложностью O(P*log2n), где P - количество потенциальных спариваний нуклеотидов, n - длина последовательности РНК. Предложен алгоритм построения оптимального выравнивания последовательностей РНК с заданной вторичной структурой относительно аффинных штрафов за делеции с временной сложностью O(m2nlog2(n)) , где m, n - длины сравниваемых последовательностей.

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

Основные результаты диссертации опубликованы в работах

биологический последовательность структура молекула

1. Roytberg M.A. A Search for Common Patterns in many Sequences // Comput. Appl. Biosci. 1992. Vol. 8, N 1. P. 57 - 64.

2. Roytberg M.A. Fast algorithm for optimal aligning of symbol sequences // In: Mathematical methods of the analysis of biopolymer sequences. AMS, Providence. 1992. P. 103-117.

3. Beridze T., Tsirekidze N., Roytberg M.A. On the tertiary structure of satellite DNA // Biochimie. 1992. Vol.74, N.1. P. 187-194.

4. Roytberg M.A. Similarity Search in Biological Sequences. // Modelling and Computer Methods in Molecular Biology and Genetics / Eds. V.A.Ratner and N.A. Kolchanov. NY: Nova Science Publishers, Inc. 1992. P. 81-86.

5. Gelfand M.S., Roytberg M.A. Prediction of the exon-intron structure by a dynamic programming approach // Biotechnology Software. 1992. P. 13-18.

6. Finkelstein, A.V. and Roytberg, M.A. Computation of biopolymers: a general approach to different problems // BioSystems. 1993. Vol.30. P.1-19.

7. Gelfand M.S., Podolsky L.I., Astakhova T.V. and Roytberg M.A. Prediction of the exon-intron structure and multicriterial optimization. //Bioinformatics and Genome Research / Eds. H.A.Lim, C.R.Cantor. Singapore: World Scientific Publ. Co. 1995. P. 173-183.

8. Gelfand M.S., Roytberg M.A. A dynamic programming algorithm for prediction of the exon-intron structure // BioSystems. 1993. Vol.30, P.173-182.

9. Nazipova N.N., Shabalina S.A., Ogurtsov A.Yu., Kondrashov A.S., Roytberg M.A., Buryakov G.V., Vernoslov S.E. SAMSON: a software package for the biopolymer primary structure analyses // Comput. Appl. Biosci. 1995. Vol. 11. P. 423-426.

10. Gelfand M.S., Podolsky L.I., Astakhova T.V., Roytberg M.A. Recognition of genes in human DNA sequences // Journal of Computational Biology. 1996. Vol. 3, N. 2. P. 223-234.

11. Ройтберг М.А., Астахова Т.В., Гельфанд М.С. Алгоритм высокоспецифичного распознавания белок-кодирующих областей в последовательностях высших эукариот // Молекуляpная биология. 1997. Т. 31, № 1. С. 25-31.

12. M.A.Roytberg, T.V.Astahova, M.S.Gelfand. Combinatorial approaches to gene recognition // Computers and Chemistry. 1998). Vol. 1, P. 229-236.

13. Sze S.H, Roytberg М.А., Gelfand M.S., Mironov А.А., Astakhova T.V., Pevzner P.A. Algorithms and software for support of gene identification experiments // Bioinformatics. 1998. Vol.1, N. 14. P. 14-19.

14. Mironov А.А., Roytberg М.А. Pevzner P.A., Gelfand M.S. Performance guarantee gene predictions via spliced alignment //Genomics. 1998. Vol. 51, P. 332-339.

15. Ройтберг М.А., Симеоненков М.Н., Таболина О.Ю. Парето-оптимальные выравнивания символьных последовательностей //Биофизика. 1998. T. 44, №4. C. 581-594.

16. Mironov AA, Koonin EV, Roytberg MA, Gelfand MS. Computer analysis of transcription regulatory patterns in completely sequenced bacterial genomes //Nucleic Acids Res. 1999. Vol.15, N.27. P. 2981-2989.

17. Ramensky V.E., Makeev V.Ju., Roytberg M.A., Tumanyan V.G. DNA segmentation through the Bayesian approach //J Comput Biol. 2000. Vol.7, N.1-2. P. 215-231.

18. Ramensky V.Е., Makeev V.Y., Roytberg M.A., Tumanyan V.G. Segmentation of long genomic sequences into domains with homogeneous composition with BASIO software // Bioinformatics. 2001. Vol.17, N.11. P. 1065-1066.

19. Kister A.E, Roytberg M.A, Chothia C., Gelfand I.M.. The sequence determinants of cadherin molecules // Protein Science. 2001. Vol. 10. P. 1801-1810.

20. Roytberg, M.A., Ogurtsov A.Y., Shabalina S.A., Kondrashov A.S. A hierarchical approach to aligning collinear regions of genomes // Bioinformatics. 2002. Vol. 18. P.1673-1680.

21. Ogurtsov A.Y., Roytberg M.A., Shabalina S.A. and Kondrashov A.S. OWEN: aligning long collinear regions of genomes // Bioinformatics. 2002. Vol. 18. P. 1703-1704.

22. Sunyaev S.R., Bogopolsky G.A., Oleynikova N.V., Vlasov P.K., Finkelstein A.V., Roytberg M.A. 2004. From analysis of protein structural alignments toward a novel approach to align protein sequences // Proteins. 2004. Vol. 54, P.569-582.

23. М.А.Ройтберг. Сравнительный анализ первичных структур нуклеиновых кислот и белков // Молекулярная биология. 2004. Т. 38, № 1. C. 92-103.

24. Kucherov, G., Noй, L. Roytberg, M. Multi-seed lossless filtration. // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2005. Vol. 2, N. 1, P. 51-61.

25. Kucherov G., Noґe L., and Roytberg M. A unifying framework for seed sensitivity and its application to subset seeds //Journal of Bioinformatics and Computational Biology. 2006. Vol. 4, N. 2. P. 553-570

26. Astakhova T.V., Petrova S.V. , Tsitovich I.I., Roytberg M.A. Recognition of coding regions in genome alignment // Bioinformatics of Genome Regulation and Structure II. / Eds. N.Kolchanov and R. Hofestaedt. NY: Springer Science+Business Media. 2006. P. 3-10.

27. Ogurtsov, A.Yu, Shabalina, S.A., Kondrashov, A.S., Roytberg M.A. Analysis of internal loops within the RNA secondary structure in almost quadratic time // Bioinformatics. 2006, Vol. 22, No. 11, P. 1317-1324

28. Литвинов И.И., Лобанов М.Ю., Миронов А.А., Финкельштейн А.В., Ройтберг М.А. Информация о вторичной структуре белка улучшает качество выравнивания // Молекулярная биология. 2006. T. 40, № 3. С. 533-540.

29. Backofen R, Chen S, Hermelin D, Landau GM, Roytberg MA, Weimann O, Zhang K. Locality and gaps in RNA comparison // J Comput Biol. 2007. Vol. 14. N 8. P.1074-1087.

30. Asthana S., Roytberg M., Stamatoyannopoulos J., Sunyaev S. Analysis of sequence conservation at nucleotide resolution // PLoS Comput Biol. 2007. V. 3, N 12. P. 254.

31. Boeva V, Clement J, Regnier M, Roytberg MA, Makeev VJ. Exact p-value calculation for heterotypic clusters of regulatory motifs and its application in computational annotation of cis-regulatory modules // Algorithms Mol Biol. 2007. Vol. 2. P.13-27

32. Polyanovsky V.O., Roytberg M.A., Tumanyan V.G. Reconstruction of genuine pair-wise sequence alignment // J. Comput. Biol. 2008. V. 15. N 4. P. 379-391.

33. Поляновский, В.О., Ройтберг, М.А., Туманян, В.Г. Новый подход к оценке достоверности выявления вставок-делеций в парном выравнивании // Биофизика. 2008. Т. 53, №4. С.533-537.

34. Корзинов О.М., Астахова Т.В., Власов П.К., Ройтберг М.А Статистический анализ участков ДНК в окрестности сайтов сплайсинга // Молекулярная биология. 2008. Т. 42. № 1: С. 150-162

35. Roytberg, M., Gambin, A., Noй, L., Lasota, S., Furletova, E., Szczurek, E., Kucherov, G. On subset seeds for protein alignment // IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2009. V. 6. N 3. P. 483-494.

36. Regnier, M., Kirakosyan, Z., Furletova E. and Roytberg, M. A Word Counting Graph // London Algorithmics 2008: Theory and Practice. / Eds. Chan, J., Daykin, J.W. and Rahman M.S. London: College Publications. 2009. P. 10-43.

37. Ройтберг М.А. Вычисление вероятностей семейств биологических последовательностей // Биофизика. 2009. Т.54. № 5. С. 718-724

Размещено на Allbest.ru