Компьютерные методы массового анализа регуляции транскрипции в бактериях

выводы.

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

2. Разработана и применена методика для проверки статистической значимости результатов эксперимента, показавшего новый дополнительный элемент основного промотора в геноме Ткегтш ациаИсш.

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

4. Создан и тестирован программный конвеер для поиска регуляторных мотивов в рамках функциональных подсистем, в который встроена процедура кластеризации.

Благодарности: Автор выражает искреннюю благодарность своим научным руководителям, Андрею Александровичу Миронову и Михаилу Сергеевичу Гельфанду, за руководство, помощь и поддержку при выполнении диссертации, а также Роману Сутормину, Всеволоду Юрьевичу Макееву, Ольге Калининой и Дмитрию Виноградову, за участие, ценные советы и продуктивное обсуждение.

Список работ, опубликованных по теме диссертации.

1. Stavrovskaya E.D., Mironov A. A. Two genetic algorithms for identification of regulatory signals // In Silico Biol. — 2003. — Vol. 3(1−2). — P. 49−56.

2. Stavrovskaya E.D., Mironov A. A. Clustering regulatory signals by binary trees // Biophysics (Moscow). — 2003. — Vol. 48 Suppl. 1. — P. S17-S20.

3. Ставровская Е. Д., Макеев В. Ю., Миронов A.A. ClusterTree-RS: алгоритм кластеризации регуляторных сигналов с помощью бинарного дерева // Молекулярная г биология, — 2006, — Т. 40. № 3. — С. 465−473.

4. Feklistov A., Barinova N., Sevostyanova A., Heyduk Е., Bass I., Vvedenskaya I., Kuznedelov K., Merkiene E., Stavrovskaya E., Klimasauskas S., Nikiforov V., Heyduk Т., Severinov K., Kulbachinskiy A. A basal promoter element recognized by free RNA polymerase sigma subunit determines promoter recognition by RNA polymerase holoenzyme//Mol Cell. — 2006, — Vol. 23. № 1, — P. 97−107.

5. Миронов А. А., Ставровская Е. Д., Макеев В. Ю. Способ исследования совместной регуляции генов бактерий и прогнозирования содержания новых регулонов и функций генов // 2006. — Патент, регистрационный номер 2 006 127 264.

6. Stavrovskaya E.D., Mironov A.A. A geneticalgorithm for identification of regulatory signals. // Proc. 3d International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2002). — Novosibirsk, Russia, 2002. Vol. 1. P. 26−27.

7. Stavrovskaya E.D., Mironov A.A. Binary tree for clusterization of regulatory signals // Proc. Moscow Conference on Computational Molecular Biology (MCCMB'03). — Moscow, Russia, 2003. P. 218−219.

8. Stavrovskaya E.D., Mironov A.A. Binary tree for clustering of regulatory signals // Proc. 4th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2004). — Novosibirsk, Russia, 2004. Vol. 1. P.195−199.

9. Stavrovskaya E.D., Mironov A.A. Binary tree for clustering of regulatory signals. // Proc. International conference BITS'2005. — Milan, Italy, 2005. P. 85.

10. Ставровская Е. Д., Миронов A.A. ClusterTree: программа кластеризации регуляторных сигналов с помощью бинарного дерева // Материалы XII Международной конференции студентов, аспирантов и молодых ученых «Ломоносов». — Москва, Россия, 2005. С. 36−37.

11. Stavrovskaya E.D., Makeev V.J., Mironov A.A. ClusterTree-RS: The binary tree algorithm for identification of co-regulated genes by clustering regulatory signals // Proc. Moscow Conference on Computational Molecular Biology (MCCMB'05). — Moscow, Russia, 2005. P. 385.

12. Stavrovskaya E.D., Makeev V.J., Merkeev I.V., Mironov A.A. Tool for automatic aetection of co-regulated genes. // Proc. 5'th European Conference on Computational Biology (ECCB'2006). — Eilat, Israel, 2007.

13. Stavrovskaya E.D., Makeev V.J., Merkeev I.V., Mironov A.A. Tool for automatics detection of co-regulated genes // Proc. 5th International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2006). —Novosibirsk, Russia, 2006. Vol.1.

P.172−175.

14. Stavrovskaya E.D., Cipriano M., Dubchak I.L., Mironov A.A., Gelfand M.S. Automated search for regulatory motifs in upstream regions of genes from the functional subsystems // Proc. Moscow Conference on Computational Molecular Biology (MCCMB'07). — Moscow, Russia, 2007. P. 283.

15. Ставровская Е. Д., Сиприано M., Дубчак И.JI., Миронов А. А., Гельфанд М. С. Автоматический поиск регуляторных сигналов перед генами в рамках функциональных подсистем. // Труды конференции Информационные технологии и системы (ИТиС'07). — Звенигород, Россия, 2007. С. 330−331.

1. Bailey Т. L., Elkan С. Fitting a mixture model by expectation maximization to discover motifs in biopolymers // Proc. Int. Conf. Intell. Syst. Mol. Biol. — 1994. — Vol. 2. — P. 28−36.

2. Bailey T. L., Elkan C. The value of prior knowledge in discovering motifs with MEME // Proc. Int. Conf. Intell. Syst. Mol. Biol. — 1995. — Vol. 3. — P. 21−29.

3. Bailey T. L., Elkan C. Unsupervised learning of multiple motifs in biopolymers using expectation maximization // Machine Learning J. — 1995. — Vol. 21. — P. 51−83.

4. Berg O.G., von Hippel P.H. Selection of DNA binding sites by regulatory proteins: Ststistical-mechanical theory and application to operators and promoters // J. Mol. Biol. — 1987. — Vol. 193(4). — P. 723−750.

5. Buhler J., Tompa M. Finding motifs using random projections // J Comput Biol. — 2002.1. Vol. 9(2). — P. 225−42.

6. Bulyk M. L. Computational prediction of transcription-factor binding site locations // Genome Biol. — 2003. — Vol. 5(1). — P. 201.

7. Bulyk M. L., Gentalen E., Lockhart D. J., Church G. M. Quantifying DNA-protein interactions by double-stranded DNA arrays // Nat Biotechnol. — 1999. — Vol. 17(6).1. P. 573−577.

8. Bulyk M. L., Huang X., Choo Y., Church G. M. Exploring the DNA-binding specificitics of zinc fingers with DNA microarrays // Proc. Natl. Acad. Sci. USA. — 2001. — Vol. 98(13).— P. 7158−7163.

9. Cardon L. R., Stormo G. D. Expectation maximization algorithm for identifying protein-binding sites with variable lengths from unaligned DNA fragments // J. Mol. Biol. — 1992, — Vol. 223(1).— P. 159−170.

10. Danilova L.V., Lyubetsky V.A., Gelfand M.S. An algorithm for identification of regulatory signals in unaligned DNA sequences, its testing and parallel implementation // In Silico Biol. — 2003, — Vol. 3(1−2).— P. 33−47.

11. Eskin E., P. Pevzner A. Finding composite regulatory patterns in DNA sequences // Bioinformatics. — 2002. — Vol. 18. Suppl 1. — P. S354−63.

12. Fraenkel Y. M., Mandel Y., Friedberg D., Margalit H. Identification of common motifs in unaligned DNA sequences: application to Escherichia coli Lrp regulon // Comput. Appl. Biosci.— 1995, — Vol. 11(4).— P. 379−387.

13. Freeh K., Herrmann G., Werner T. Computer-assisted prediction, classification, and delimitation of protein binding sites in nucleic acids // Nucleic Acids Res. — 1993. — Vol. 21(7).— P. 1655−1664.

14. Frishman D., Mironov A., Gelfand M. Starts of bacterial genes: estimating the reliability of computer predictions // Gene. — 1999. — Vol. 234(2). — P. 257−65.

15. Gelfand M. S., Koonin E. V., Mironov A. A. Prediction of transcription regulatory sites in Archaea by a comparative genomic approach // Nucleic Acids Res. — 2000. — Vol. 28(3). — P. 695−705.

16. Geman S., Geman D. Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1984. — Vol. 6, — P. 621−641.

17. Gold L., Brown D., He Y., Shtatland T., Singer B. S., Wu Y. From oligonucleotide shapes to genomic SELEX: novel biological regulatory loops // Proc. Natl. Acad. Sci. USA. — 1997. — Vol. 94(1). — P. 59−64.

18. Grundy W. N., Bailey T. L., Elkan C. P. ParaMEME: a parallel implementation and a web interface for a DNA and protein motif discovery tool // Comput Appl Biosci. — 1996. — Vol. 12(4).— P. 303−310.

19. Gurkiewicz M., Korngreen A. Free in PMC A numerical approach to ion channel modelling using whole-cell voltage-clamp recordings and a genetic algorithm // PLoS Comput. Biol. — 2007. — Vol. 3(8). — P. 169.

20. Hartigan J. A., Wong M. A. A K-means clustering algorithm // Applied Statistics. — 1979.— Vol. 28(1).— P. 100−108.

21. Hertz G. Z., Stormo G. D. Identifying DNA and protein patterns with statistically significant alignments of multiple sequences // Bioinformatics. — 1999. — Vol. 15(7−8) .1. P. 563−577.

22. Hertz G. Z., Hartzell G. W. 3rd, Stormo G. D. Identification of consensus patterns in unaligned DNA sequences known to be functionally related // Comput. Appl. Biosci. — 1990. — Vol. 6(2). — P. 81−92.

23. Horak C. E., Mahajan M. C., Luscombe N. M., Gerstein M., Weissman S. M., Snyder M. GATA-1 binding sites mapped in the beta-globin locus by using mammalian chip-chip analysis // Proc. Natl. Acad. Sci. U S A. — 2002. — Vol. 99(5). — P. 2924−2929.

24. Hsieh S.Y., Tseng C.L., Lee Y.S., Kuo A.J., Sun C.F., Lin Y.H., Chen J.K. Abstract Highly efficient classification and identification of human pathogenic bacteria by MALDI-TOF MS // Mol. Cell. Proteomics. — 2008. — Vol. 7(2). — P. 448−56.

25. Hu Y. J., Sandmeyer S., McLaughlin C., Kibler D. Combinatorial motif analysis and hypothesis generation on a genomic scale // Bioinformatics. — 2000. — Vol. 16(3). — P. 222−32.

26. Hubert L. Approximate Evaluation Techniques for the Single-Link and Complete-Link Hierarchical Clustering Procedures // Journal of the American Statistical Association. — 1974. — Vol. 69(347). — P. 698−704.

27. Hughes J.D., Estep P.W., Tavazoie S., Church G.M. Computational identification of cis-regulatory elements associated with groups of functionally related genes in Saccharomyces cerevisiae//J. Mol. Biol. — 2000. — Vol. 296(5). — P. 1205−1214.

28. Iyer V. R., Horak C. E., Scafe C. S., Botstein D., Snyder M., Brown P. O. Genomic binding sites of the yeast cell-cycle transcription factors SBF and MBF.// Nature. 2001. Vol. 409(6819). P. 533−538.

29. Jain A.K., Murty M.N., Flynn P.J. Data Clustering: A Review.// ACM Computing Surveys (CSUR). 1999. Vol. 31(3). P. 264−323.

30. Jensen L. J., Knudsen S. Automatic discovery of regulatory patterns in promoter regions based on whole cell expression data and functional annotation // Bioinformatics. — 2000. — Vol. 16(4).— P. 326−333.

31. Johnson DS, Mortazavi A, Myers RM, Wold B. Genome-wide mapping of in vivo proteinDNA interactions // Science. — 2007. — Vol. 316(5830). — P. 1497−1502.

32. Jonassen I. Efficient discovery of conserved patterns using a pattern graph // Comput. Appl. Biosci. — 1997. — Vol. 13(5). — P. 509−522.

33. Kel-Margoulis O.V., Ivanova T.G., Wingender E., Kel A.E. Automatic annotation of genomic regulatory sequences by searching for composite clusters // Pac. Symp. Biocomput.— 2002, — P. 187−198.

34. Kielbasa S. M., Korbel J. O., Beule D., Schuchhardt J., Herzel H. Combining frequency and positional information to predict transcription factor binding sites // Bioinformatics. —2001, — Vol. 17(11).— P. 1019−1026.

35. Kullback S. Information theory and statistics // Mineola, N.Y., Dover Publications. ¦— 1997.

36. Lawrence C. E., Reilly A. A. An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences // Proteins. — 1990. — Vol. 7(1). — P. 41−51.

37. Lawrencc C. E., Altschul S. F., Boguski M. S., Liu J. S., Neuwald A. F., Wootton J. C. Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment // Science. — 1993, — Vol. 262(5131). — P. 208−214.

38. Lee H.G., Lee H.S., Jeon S.H., Chung T.H., Lim Y.S., Huh W.K. High-resolution analysis of condition-specific regulatory modules in Saccharomyces cerevisiae // Genome Biol. — 2008. — Vol. 9. — P. R2.

39. Lee Z.J. An integrated algorithm for gene selection and classification applied to microarray data of ovarian cancer // Artif. Intell. Med. — 2008. — Vol. 42(1). — P. 81−93.

40. Liu X., Brutlag D. L., Liu J. S. BioProspector: discovering conserved DNA motifs in upstream regulatory regions of co-expressed genes // Pac. Symp. Biocomput. — 2001. — P. 127−138.

41. Liuni S., Prunella N., Pesole G., D’Orazio T., Stella E., Distante A. SIMD parallelization of the WORDUP algorithm for detecting statistically significant patterns in DNA sequences // Comput. Appl. Biosci. — 1993. — Vol. 9(6). — P. 701−707. •.

42. Lukashin A. V., Engelbrccht J., Brunak S. Multiple alignment using simulated annealing: branch point definition in human mRNA splicing // Nucleic Acids Res. — 1992. — Vol. 20(10).— P. 2511−2516.

43. Makita Y., Nakao M., Ogasawara N., Nakai K. DBTBS: database of transcriptional regulation in Bacillus subtilis and its contribution to comparative genomics // Nucleic Acids Res. — 2004. — Vol. 32. — P. 75−77.

44. Marsan L., Sagot M. F. Algorithms for extracting structured motifs using a suffix tree with an application to promoter and regulatory site consensus identification // J. Comput. Biol.2000. — Vol. 7(3−4). — P. 345−62.

45. McClure W.R. Mechanism and control of trancription initiation in prokaryotes // Ann. Rev. Biochem.— 1985.— Vol.54. — P. 171−204.

46. Merkeev I.V., Novichkov P. S., Mironov A.A. PHOG: a database of supergenomes built from proteome complements // BMC Evol. Biol. — 2006. — Vol. 22. — P. 6−52.

47. Metropolis N., Rosenbluth M.N., Teller A.H., Teller E. Equations of state calculations by fast computing machines// J. Chem. Phys.— 1953.— Vol.21. — P. 1087−1092.

48. Mironov A.A., Vinokurova N.P., Gel’falnd M.S. Software for analyzing bacterial genomes // Mol. Biol. (Mosk). — 2000. — Vol. 34(2). — P. 253−262.

49. Overbeek R. et al. The Subsystems Approach to Genome Annotation and its Use in the Project to Annotate 1000 Genomes // Nucleic Acids Research. — 2005. — Vol. 33(17). — P. 5691−5702.

50. Pesole G., Prunella N., Liuni S., Attimonelli M., Saccone C. WORDUP: an efficient algorithm for discovering statistically significant patterns in DNA sequences // Nucleic Acids Res.— 1992.— Vol. 20(11).— P. 2871−2875.

51. Pevzner P. A., Sze S. H. Combinatorial approaches to finding subtle signals in DNA sequences // Proc. Int. Conf. Intell. Syst. Mol. Biol. — 2000. — Vol. 8. — P. 269−278.

52. Prasad P.A., Kanagasabai V., Arunachalam J., Gautham N. Exploring conformational space using a mean field technique with MOLS sampling // J. Biosci. — 2007. — Vol. 32(5). — P. 909−920.

53. Qin Z.S., McCue L.A., Thompson W., Mayerhofer L., Lawrence C.E., Liu J.S. Identification of co-regulated genes through Bayesian clustering of predicted regulatory binding sites // Nat Biotechnol. — 2003. — Vol. 21(4). — P. 435−439.

54. Quandt K., Freeh K., Karas H., Wingender E., Werner T. Matlnd and Matlnspector: new fast and versatile tools for detection of consensus matches in nucleotide sequence data // Nucleic Acids Res. — 1995.— Vol. 23(23). — 4878−4884.

55. Reid J. L., Iyer V. R., Brown P. O., Struhl K. Coordinate regulation of yeast ribosomal protein genes is associated with targeted recruitment of Esal histone acetylase // Mol. Cell. — 2000. — Vol. 6(6). — P. 1297−1307.

56. Ren B., Cam H., Takahashi Y., Volkert T., Terragni J., Young R. A., Dynlacht B. D. E2 °F integrates cell cycle progression with DNA repair, replication, and G (2)/M checkpoints // Genes Dev. — 2002. — Vol. 16(2). — P. 245−256.

57. Rigoutsos I., Floratos A. Combinatorial pattern discovery in biological sequences: The TEIRESIAS algorithm // Bioinformatics. — 1998. — Vol. 14(1). — P. 55−67.

58. Robison K., McGuire A.M., Church G.M. A comprehensive library of DNA-binding site matrices for 55 proteins applied to the complete Escherichia coli K-12 genome // J. Mol. Biol.— 1998.— Vol. 284(2).— P. 241−254.

59. Rocke E., Tompa M. An algorithm for finding novel gapped motifs in DNA sequences // Proceedings of the second annual international conference on Computational molecular biology RECOMB '98. — 1998. — P. 228−233.

60. Rodionov D.A., Gelfand M.S. Identification of a bacterial regulatory system for ribonucleotide reductases by phylogenetic profiling // Trends Genet. — 2005. — Vol. 21(7).— P. 385−389.

61. Rosenbluth J.M., Mays D.J., Pino M.F., Tang L.J., Pietenpol J.A. A Gene Signature-Based Approach Identifies mTOR as a Regulator of p73 // Molecular and Cellular Biology. — 2008. — Vol. 28(19). — P. 5951−5964.

62. Roth F. P., Hughes J. D., Estep P. W., Church G. M. Finding DNA regulatory motifs within unaligned noncoding sequences clustered by whole-genome mRNA quantitation // Nat. Biotechnol. — 1998.— Vol. 16(10).— P. 939−945.

63. Rouchka E.C. A Brief Overview of Gibbs Sampling // Washington University Institute for Biomedical Computing Statistics Study Group. — 1997.

64. Sattath S., Tversky A. Additive similarity trees // Psychometrika. — 1977. — Vol. 42(3) .1. P. 19−345.

65. Schujman G.E., Paoletti L., Grossman A.D., de Mendoza D. FapR, a bacterial transcription factor involved in global regulation of membrane lipid biosynthesis // Dev. Cell. — 2003.1. Vol. 4(5). — P. 663−672.

66. Shannon C. E., Weaver W. The mathematical theory of communication // Urbana, University of Illinois Press. — 1949.

67. Stormo G. D., Hartzell G. W. 3rd. Identifying protein-binding sites from unaligned DNA fragments // Proc. Natl. Acad. Sci. USA.— 1989. — Vol. 86(4). — P. 1183−1187.

68. Stormo G. D. DNA binding sites: representation and discovery // Bioinformatics. — 2000 .— Vol. 16(1).— P. 16−23.

69. Tatusov R.L., Koonin E.V., Lipman D.J. A genomic perspective on protein families // Science.— 1997.— Vol. 278(5338). — P. 631−637.

70. Thijs G., Marchal K., Lescot M., Rombauts S., De Moor B., Rouze P., Moreau Y. A Gibbs sampling method to detect overrepresented motifs in the upstream regions of coexpressed genes.// J Comput Biol. 2002. Vol. 9(2). P. 447−464.

71. Tompa M. An exact method for finding short motifs in sequences, with application to the ribosome binding site problem // Proc. Int. Conf. Intell. Syst. Mol. Biol. — 1999. — P. 262−271.

72. Tompa R., McCallum C. M., Delrow J., Henikoff J. G., van Steensel B., Henikoff S. Genome-wide profiling of DNA methylation reveals transposon targets of CHROMOMETHYLASE3 // Curr. Biol. — 2002. — Vol. 12(1). — P. 65−68.

73. Vinogradov D.V., Mironov A.A. SiteProb: yet another algorithm to find regulatory signals in nucleotide sequences // Proceedings of the third international conference BGRS'2002. — 2002. — Vol. 1. — P. 30−32.

74. Wade J.T., Struhl K., Busby S.J., Grainger D.C. Genomic analysis of protein-DNA interactions in bacteria: insights into transcription and chromosome organization // Mol. Microbiol. — 2007. — Vol. 65(1). — P. 21−26.

75. Waterman M. S. Multiple sequence alignment by consensus // Nucleic Acids Res. — 1986, — Vol. 14(22). — P. 9095−9102.

76. Weinmann A. S., Yan P. S., Oberley M. J., Huang T. H., Farnham P. J. Isolating human transcription factor targets by coupling chromatin immunoprecipitation and CpG island microarray analysis // Genes Dev. — 2002. — Vol. 16(2). — P. 235−244.

77. Wolfertstetter F., Freeh K., Herrmann G., Werner T. Identification of functional elements in unaligned nucleic acid sequences by a novel tuple search algorithm // Comput. Appl. Biosci.— 1996, — Vol.— 12(1).— P. 71−80.

78. Wolfsberg T. G., Gabrielian A. E., Campbell M. J., Cho R. J., Spouge J. L., Landsman D. Candidate regulatory sequence elements for cell cycle-dependent transcription in Saccharomyces cerevisiae // Genome Res. — 1999. — Vol. 9(8). — P. 775−792.

79. Wyrick J. J., Young R. A. Deciphering gene expression regulatory networks // Curr. Opin. Genet. Dev. — 2002, — Vol. 12(2).— P. 130−136.

80. Xu X., Wang L., Ding D. Learning module networks from genome-wide location and expression data // FEBS Lett. — 2004. — Vol. 578(3). — P. 297−304.

81. Zhang H., Switzer R.L. Transcriptional pausing in the Bacillus subtilis pyr operon in vitro: a role in transcriptional attenuation? // J. Bacteriol. — 2003. — Vol. 185(16). — P. 4764−4771.

82. Миронов А. А., Гельфанд М. С. Компьютерный анализ регуляторных сигналов в полных бактериальных геномах // Молекулярная Биология (Москва). — 1999. — 33(5). — С. 772−778.