Разработка алгоритмов и программ для изучения регулярного строения последовательностей ДНК
Диссертация
При использовании динамического программирования и некоторых других подходов серьезным ограничением для выявления периодичности является поиск идентичных совпадений символов между последовательностями при выявлении повторов. Под идентичными совпадениями понимаются совпадения вида s (i)s (i), i=l, ., h, где s (i) — символ алфавита последовательности, h — размер алфавита символьной… Читать ещё >
Содержание
- ГЛАВА 1. ОБЗОР МАТЕМАТИЧЕСКИХ МЕТОДОВ АНАЛИЗА НУКЛЕОТИДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И ИХ КОМПЬЮТЕРНОЙ РЕАЛИЗАЦИИ
- 1. 1. Структурная организация последовательностей ДНК
- 1. 2. Математические методы поиска микросателлитных последовательностей
- 1. 3. Математические методы классификации периодических последовательностей ДНК
- 1. 4. Базы данных микросателлитных последовательностей ДНК
- 1. 5. Веб-серверы поиска микросателлитных последовательностей
- 1. 6. Периодичность бактериальных и растительных геномов и промоторных районов ДНК, обнаруженная существующими методами
- ГЛАВА 2. РАЗРАБОТКА НОВЫХ АЛГОРИТМОВ И ПРОГРАММ ДЛЯ ВЫЯВЛЕНИЯ РЕГУЛЯРНОСТИ В ПОСЛЕДОВАТЕЛЬНОСТЯХ ДНК
- 2. 1. Разработанные алгоритмы
- 2. 1. 1. Алгоритм выявления регулярности последовательностей ДНК
- 2. 1. 2. Алгоритм тассификации периодичности последовательностей ДНК
- 2. 1. 3. Алгоритм модифицированного профильного анализа для выявления скрытой периодичности в последовательностях ДНК
- 2. 2. Использованные методы
- 2. 2. 1. Методы создания базы данных скрытой периодичности последовательностей ДНК
- 2. 2. 2. Методы создания веб-сервера для поиска скрытой периодичности в последовательностях ДНК
- 2. 1. Разработанные алгоритмы
- 3. 1. Регулярность строения промоторных участков ДНК
- 3. 2. Классификация скрытой периодичности последовательностей ДНК
- 3. 3. Выявление микросателлитных. последовательностей алгоритмом модифицированного профильного анализа
- 3. 4. База данных скрытой периодичности последовательностей ДНК
- 3. 5. Программная реализация веб-сервера для поиска скрытой периодичности последовательностей ДНК
Список литературы
- Молекулярная биология: Структура и биосинтез нуклеиновых кислот: Учеб. для биол. спец. вузов / В. И. Агол, А. А. Богданов, В. А. Гвоздев и др.- Под ред. А. С. Спирина.- М.: Высшая школа, 1990. 352 е., ил.
- Гены и геномы: В 2-х т. / М. Сингер, П. Берг. Т. 1. Пер. с англ. М.: Мир, 1998. — 373 е., ил.
- Le Fleche P., Наиск Y., Onteniente L., et al. A tandem repeats database for bacterial genomes: application to the genotyping of Yersinia pestis and Bacillus anthracis // BMC Microbiology. 2001. -Vol. 1, No. 2.
- Wells R. Molecular basis of genetic instability of triplet repeats // J. Biol. Chem. 1996. — Vol. 271.1. P. 2875−2878.
- Weitzmann M., Woodford K., Usdin K. DNA secondary structures and the evolution of hypervariabletandem arrays II J. Biol Chem. 1997. — Vol. 272. — P. 9517−9523.
- Richards R., Holman K., Yu S. Sutherland G. Fragile X syndrome unstable element, p (CCG)n, andother simple tandem repeat sequences are binding sites for specific nuclear proteins // Hum. Mol. Genet. 1993. — Vol. 2. — P. 1429−1435.
- Lu O., Wallrath L., Granok II. Elgin S. (CT)n (GA)n repeats and heat shock elements have distinctroles in chromatin structure and transcriptional activation of the Drosophila hsp26 gene // Mol. Cell. Biol. 1993. — Vol. 13. — P. 2802−2814.
- Keim P., Price L.B., Klevytska A.M., et al. Multiple-Locus Variable-Number Tandem Repeat Analysis
- Reveals Genetic Relationships within Bacillus anthracis II J. Bacteriol. 2000. — Vol. 182. — P. 29 282 936.9. loth G., Gaspari Z., Jurka J. Microsatellites in different eukaryotic genomes: survey and analysis //
- Genome Res. 2000. — Vol. 10. — P. 967−981.
- Gur-Arie R., Cohen С J., Eitan Y., Shelef L., Hallerman E.M., Kashi Y. Simple sequence repeats in
- Escherichia coli: abundance, distribution, composition, and polymorphism // Genome Res. 2000. -Vol. 10.-P. 62−71.
- Adair D.M., Worsham P.L., Hill K.K., et al. Diversity in a variable-number tandem repeat from Yersinia pestis II J. Clin. Microbiol. 2000. — Vol. 38. — P. 1516−1519.
- Riley D.E., Krieger J.N. X Chromosomal short tandem repeat polymorphisms near thephosphoglycerate kinase gene in men with chronic prostatitis // Biochim Biophys Acta. 2002. -Vol. 1586, No. l.-P. 99−107.
- Mishra D., Thangaraj K, Mandhani A., Kumar A., Mittal R. Is reduced CAG repeat length inandrogen receptor gene associated with risk of prostate cancer in Indian population? // Clin. Genet. -2005. Vol. 68, No. 1. — P. 55−60.
- Small, S., Kraut, R., Hoey, Т., Warrior, R., Levine, M. Transcriptional regulation of a pair-rule stripein Drosophila // Genes Dev. 1991. — Vol.5. — P. 827−839.
- Pedersen A.G. et al. The biology of Eukaryotic promoter prediction: a review // Сотр. Chem. — 1999.-Vol. 23.-P. 191−207.
- Herzel H., Trifonov E.N., Weiss O., Grobe I. Interpreting correlations in biosequences // Physica A. —1998. Vol. 249. — P.449−459.
- Herzel H" Weiss O., Trifonov E.N. 10−11 bp periodicities in complete genomes reflect proteinstructure and DNA folding // Bioinformatics. 1999. — Vol. 15, No. 3. — P.187−193.
- Korotkov E. V., Korotkova M.A., Kudryashov N.A. Information decomposition method to analyzesymbolical sequences // Phys. Let. A. 2003. — Vol. 312. — P.198−210.
- Makeev V.Y., Frank G. K, Tumanyan KG. Statistics of periodic patterns in the sequences of humanintrons // Biophysics. 1996. — Vol. 41, No.l. — P. 263−268.
- Chechetkin V.R., Turygin A.Y. Size dependence of three-periodicity and long range correlations in
- DNA sequences // Phys.Lett. A. 1995. — Vol. 199. — P. 75−80.
- Chechetkin V.R., Lobzin V. V. Levels of ordering in coding and noncoding regions of DNA sequences
- Phys. Lett. A. -1996. Vol. 222. — P. 354−360.
- Chechetkin V.R., Lobzin V. V. Study of correlations in segments DNA sequences: application tostructural coupling between exons and introns I I J.Theor.Biol. — 1998. Vol. 190. — P. 69−83.
- Лобзии B.B., Чечеткии B.P. Порядок и корреляции в геномных последовательностях ДНК.
- Спектральный подход // Успехи физических наук. — 2000. Т. 170, № 1. — С. 57−81.
- Tiwari S., Ramachandran S., Bhattacharya A., Bhattacharya S., Ramaswamy R. Prediction ofprobable genes by Fourier analysis of genomic sequences // CABIOS. — 1997. Vol.13. — P. 263 270.
- Needleman S.B., Wunsch C.D. A general method applicable to the search for similarities in the aminoacid sequence of two proteins // J. Mo I. Biol. 1970. — Vol. 48, No. 3. — P. 443−453.
- Математические методы для анализа последовательностей ДНК. Пер. с англ. / Под. ред. М.С.
- Уотермена М.: Мир, 1999. — 349 с.
- Coward Е., Drablos F. Detecting periodic patterns in biological sequences // Bioinformatics. — 1998.- Vol. 14, No. 6. P. 498−507.
- Benson G. Tandem repeats finder: a program to analyse DNA sequences // Nucleic Acids Res. 1999.-Vol. 27. P. 573−580.
- Benson G. Sequence alignment with tandem duplications // J.Comput.Biol. 1997. — Vol. 4. — P. 351 367.
- Landau G., Schmidt. /// Proceedings. of the IV annual symposium on combinatorial patterns matching, 1. cture notes in computer science. 1993. — Vol. 648. — P. 120−133.
- Karlin S., Morris M., Ghandour G., Leung M.-Y. Efficient algorithms for molecular sequence analysis
- Proc. Natl. Acad. Sci. USA. 1988. — Vol. 85. — P. 841−845.
- Benson G., Waterman M. A method for fast database search for all k-nucleotide repeats // Nucleic
- Acids Res. 1994. — Vol. 22. — P. 4828−4836.
- Sagot M., Myers E. Proceedings of the II annual international conference on computational molecularbiology. New-York: AMC press, 1998. P. 20−29.
- Miller JV., Myers E. Approximate matching of regular expressions // Bull.Math. Biol. 1989. — Vol.51.-P. 5−37.
- Kannan S.K., Myers E. W. An Algorithm for Locating Nonoverlapping Regions of Maximum
- Alignment Score // SIAMJ. Comput. 1996. — Vol. 25. — P. 648−662.
- Schmidt J. P. All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings // SIAMJ. Comput. 1998. — Vol. 27. — P. 972−992.
- Gribskov M., McLachlan A.D., Eisenberg D. Profile analysis: detection of distantly related proteins // Proc. Natl. Acad. Sci. USA. 1987. — Vol. 84. — P. 4355−4358.
- DayhoffM.O. Atlas of protein sequence and structure // Natl. Biomed. Res. Found. 1979. Vol. 5, No. 3. — P. 353−358.
- Gribskov M, Burgess R.R. Sigma factors from E. coli. B. subtilis, phage SP01, and phage T4 are homologous proteins // Nucleic Acids Res. 1986. — Vol. 14. — P. 6745−6763.
- Patthy L. Detecting homology of distantly related proteins with consensus sequences // J. Mol. Biol. -1987.-Vol. 198. -V.561−511.
- Tatusov R.L., Altschul S.F., Koonin E. V. Detection of conserved segments in proteins: iterative scanning of sequence databases with alignment blocks // Proc. Natl. Acad. Sci. USA. — 1994. Vol. 91.-P. 12 091−12 095.
- Yi T.M., Lander E.S. Recognition of related proteins by iterative template refinement (ITR) II Protein Sci. -1994.-Vol. 3.-P. 1315−1328.
- Henikoff S., Henikoff J.G. Position-based sequence weights // J. Mol. Biol. 1994. — Vol. 243. -P.574−578.
- Altschul S.F., Koonin E.V. Iterated profile searches with PSI-BLAST—a tool for discovery in protein databases // Trends Biochem. Sci. 1998. — Vol. 23. — P. 444−447.
- Vingron M., Argos P. A fast and sensitive multiple sequence alignment algorithm // Comput. Appl. Biosci. 1989. — Vol. 5. — P.115−121.
- Sander C., Schneider R. Database of homology-derived protein structures and the structural meaning of sequence alignment // Proteins. 1991. — Vol. 9. — P. 56−68.
- Karchin R., Hughey R. Weighting hidden Markov models for maximum discrimination // Bioinformatics. 1998. Vol. 14. — P. 772−782.
- Valdar IV.S. Scoring Residue Conservation // Proteins. 2002. — Vol. 48. — P. 227−241.
- Sunyaev S.R., Eisenhaber F., Rodchenkov I.V., Eisenhaber B.E., Tumanyan KG., Kuznetsov E.N. PSIC: profile extraction from sequence alignments with position-specific counts of independent observations // Protein Eng. 1999.-Vol. 12. — P.387−394.
- May A.C. Optimal classification of protein sequences and selection of representative sets from multiple alignments: application to homologous families and lessons for structural genomics // Protein Eng. 2001. — Vol. 14. — P. 209−217.
- Durbin R., Eddy S., Krogh A., Mitchison G. Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge (UK): Cambridge University Press, 1998.
- Sibbald P.R., Argos P. Weighting aligned protein or nucleic acid sequences to correct for unequal representation // J. Mol. Biol. 1990. — Vol. 216. — P. 813−818.
- Altschul S.F., Lipman D.J. Equal animals // Nature. 1990. — Vol. 348. — P. 493194.
- Gerstein M., Sonnhammer E., Chothia C. Volume changes in protein evolution // J. Mol. Biol. 1994. -Vol. 236. — P.1067−1078.
- Kolpakov R., Bana G., Kucherov G. mreps: efficient and flexible detection of tandem repeats in DNA II Nucleic Acids Res. 2003. — Vol. 31, No. 13. — P. 3672−3678.
- Rice P., Longden I., Bleasby A. EMBOSS: The european molecular biology open software suite // Trends Genet. 2000. — Vol. 16. — P. 276−277.
- Milosavljevic A., JurkaJ. Discovering simple DNA sequences by the algorithmic significance method // CABIOS. 1993. — Vol. 9. — P. 407−411.
- Landau G., Schmidt J., Sokol D. An algorithm for approximate tandem repeats // J. Сотр. Biol. -2001.-Vol. 8.-P. 1−18.
- Subramanian S., Mishra R.K., Singh L. Genome-wide analysis of microsatcllite repeats in humans: their abundance and density in specific genomic regions // Genome Biol. 2003. — Vol. 4, No. 2. — P. R13
- Swati D. In silico comparison of bacterial strains using mutual information // J. Biosci. — 2007. — Vol. 32, No. 6.-P. 1169−1184.
- Ferragina P., Giancarlo R., Greco V., Manzini G., Valiente G. Compression-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment // BMC Bioinformatics. 2007. — Vol. 8, No. 252.
- Li M., Chen X, Li X, Ma В., Vitany P. The Similarity Metric // IEEE T. Inform. Theory. 2004. -Vol. 50, No. 12. — P. 3250−3264.
- NaikP.K., Mittal V.K., Gupta S. RetroPred: A tool for prediction, classification and extraction of non-LTR retrotransposons (LINEs & SINEs) from the genome by integrating PALS, PILER, MEME and ANN // Bioinformation. 2008. — Vol. 2, No. 6. — P. 263−270.
- Ruitberg C.M., Reeder D.J., Butler J.M. STRBase: a short tandem repeat DNA database for the human identity testing community // Nucleic Acids Res. 2001. — Vol. 29. — P. 320−322.
- Bohy Т., Patch A.-M., Axes S. J. TRbase: a database relating tandem repeats to disease genes for thehuman genome // Bioinformatics. 2005. — Vol. 21, No. 6. — P. 811−816.
- Macas J., Meszaros Т., Nouzova M. PlantSat: a specialized database for plant satellite repeats //
- Bioinformatics. 2002. — Vol. 18. — P. 28−35.
- Sreenu V., Alevoor V., Nagaraju J., Nagarajaram H.A. MICdb: Database of Prokaryotic
- Microsatellites // Nucleic Acids Res. 2003. — Vol. 31. — P.106−108.
- Collins J.R., Stephens R.M., Gold В., Long В., Dean M., Burt S.K. An exhaustive DNA micro-satellitemap of the human genome using high performance computing // Genomics. 2003. Vol. 82, No. 1. -P. 10−19.
- Chang СЛ., Chang Y.C., Underwood A., Chiou C.S., Kao C.Y. VNTRDB: a bacterial variablenumber tandem repeat locus database // Nucleic Acids Res. 2007. — Vol. 35 (database issue). — P. 416−421.
- Wexler Y., Yakhini Z, Kashi Y, Geiger D. Finding Approximate Tandem Repeats in Genomic1. Sequences // RECOMB 2004.
- Bikandi, J., San Millan, R., Rementeria, A., Garaizar, J. In silico analysis of complete bacterialgenomes: PCR, AFLP-PCR, and endonuclease restriction // Bioinformatics. 2004. — Vol. 20, No. 5. — P. 798−799.
- Prasad M.D., Muthulakshmi M., Arunkumar K.P., Madhu M., Sreenu V.B., Pavithra V., Bose В.,
- Nagarajaram H.A., Mita K" Shimada Т., Nagaraju J. SilkSatDb: a microsatellite database of the silkworm. Bombyx mori // Nucleic Acids Res. 2005. — Vol. 33(Database issue). — P. D403−6.
- Sreenu КВ., Ranjitkumar G., Swaminathan S., PriyaS., Bose В., Pavan M.N., Thanu G., Nagaraju J.,
- Nagarajaram H.A. MICAS: A fully automated web server for microsatellite extraction and analysisfrom prokaryote and viral genomic sequences // Applied Bioinformatics. 2003. — Vol. 2. — P. 165 168.
- Smit A.F.A., Hubley R. Green P., unpublished data. Current Version: open-3.1.9 (RMLib: 20 071 204).
- Kohany O., Gentles A.J., Hankus L., Jurka J. Annotation, submission and screening of repetitiveelements in Repbase: RepbaseSubmitter and Censor //
- BMC Bioinformatics. 2006. — Vol. 7, No. 474.
- Sharma D., Jssac В., Raghava G.P., Ramaswamy R. Spectral Repeat Finder (SRF): identification ofrepetitive sequences using Fourier transformation // Bioinformatics. 2004. — Vol. 20. — P. 14 051 412.
- Cleland C. A, Leach R. W., Forst C. Tandyman, 2000, Los Alamos National Laboratory, unpublished.
- Smitlders M.J.M., Van Der Shoot J., Arens P., Vosman B. Trinucleotide repeat microsatellite markers for black poplar (Populus nigra L.) // Mol. Ecol. Notes. 2001. — Vol. 1. — P. 188−190.
- Thompson H., Schmidt R., Dean C. Identification and distribution of seven classes of middle-repetitive DNA in the Arabidopsis thaliana genome // Nucleic Acids Res. 1996. — Vol. 24, No. 15. -P.3017−3022.
- Li, Y-C., Fahima Т., Roder M.S. et al. Genetic effects on microsatellite diversity in wild emmer wheat (Triticum dicoccoides) at the Yehudiyya microsite, Israel // Heredity. 2003. — Vol. 90. — P. 150−156.
- Yaish M.W.F., Perez de la Vega M. Isolation of (GA)n Microsatcllite Sequences and Description of a Predicted MADS-box Sequence Isolated from Common Bean (Phaseolus vulgaris L.) // Genet. Mol. Biol. 2003. — Vol. 26, No. 3. — P. 337−342.
- Benson G. Tandem Cyclic Alignment, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching // LNCS 2001. Vol. 2089. — P. 118−130.
- Lngham L.D., Hanna W.W., Baier J.W., Hannah L.C. Origin of the main class of repetitive DNA within selected Pennisetum species // Mol Gen. Genet. 1993. — Vol. 238. — P. 350−356.
- Moore G., Cheung IV., Schwarzacher Т. Flavell R.B. BIS 1, a major component of the cereal genome and a tool for studying genomic organization // Genomics. 1991. — Vol. 10. — P. 469−476.
- Smyth D.R. Dispersed repeats in plant genomes // Chromos. 1991. Vol. 100. — P. 355−359.
- Hake S., Walbot V The genome of Zea mays, its organization and homology to related grasses // Chromos. 1980. — Vol. 79. — P. 251−270.
- Wang Z., Weber J.L., Zhong G., Tanksley S.D. Survey of plant short tandem DNA repeats // Theor. Appl. Genet. 1994. — Vol. 88. — P. 1−6.
- Gupta P.K., Varshney R.K. The development and use of microsatellite markers for genetic analysis of plant breeding with emphasis on bread wheat // Euphytica. 2000. — Vol. 113. — P. 163−185.
- Groathouse N.A., Rivoire В., Kim H" Lee H., Cho S.-T. et al. Multiple Polymorphic Loci for Molecular Typing of Strains of Mycobacterium leprae II J. Clin. Microbiol. 2004. — Vol. 42, No. 4. -P. 1666−1672.
- MrazekJ., Guo X., Shah A. Simple sequence repeats in prokaryotic genomes // Proc. Natl. Acad. Sci. USA. 2007. — Vol. 104, No. 20. — P. 8472−8477.
- Ussery D. W, Binnewies Т. Т., Gouveia-Oliveira R., Jarmer H" Hallin P. F. Genome Update: DNA repeats in bacterial genomes // Microbiology. 2004. — Vol. 150. — P. 3519−3521.
- Ohler U" Liao G.C., Niemann K, Rubin G.M. Computational analysis of core promoters in the Drosophila genome // Genome Biol. 2002. — Vol. 3, No. 12. — P. 0087.1−0087.12.
- Knudsen S. Promoter2.0: for the recognition of PoIII promoter sequences // Bioinformatics. — 1999. -Vol. 15, No. 5.-P. 356−361.
- Bajic V.B., Seah S.H. Dragon gene start finder: an advanced system for finding approximate locations of the start of gene transcriptional units // Genome Res. 2003. — Vol. 13. — P. 1923−1929.
- Solovyev V. V., Shahmuradov I.A. PromH: promoters identification using orthologous genomic sequences // Nucleic Acids Res.- 2003. Vol. 31. — P. 3540−3545.
- Bajic V.B. et al. Promoter prediction analysis on the whole human genome // Nat. Biotechnol. 2004. -Vol. 22.-P. 1467−1473.
- Xie X., Wu S., Lam K.-M., Yan H. PromoterExplorer: an effective promoter identification method based on the AdaBoost algorithm // Bioinformatics. 2006. — Vol. 22. — P. 2722−2728.
- Frenkel F.E., Chaley M.B., Korotkov E.V., Skryabin KG. Evolution of tRNA-like sequences and genome variability // Gene. 2004. — Vol. 335. — P.57−71.
- Korotkov E.V., Korotkova M.A., Rudenko KM. MIR: family of repeats common for vertebrate genomes // Mol. Biol. (Mosk). 2000. — Vol. 34, No. 4. — P. 553−559.
- HoelP.G. Introduction to Mathematical Statistics, 3rd ed. New-York: Wiley, 1966.
- Браунли К. А. Статистическая теория и методология в науке и технике. Пер с англ. М.: Наука. 1977.-407 с.
- Sheskin D.J. Handbook of Parametric and Nonparametric Statistical Procedures. 2nd ed. New York: Chapman & Hall/CRC, 2000.
- Shelenkov A.A., Skryabin KG., Korotkov E. К Search and Classification of Potential Minisatellite Sequences from Bacterial Genomes II DNA Res. 2006. — Vol. 13, No. 3. — P. 89−102.
- Waterman M.S. Introduction to Computational Biology. Map, Sequences and Genomes. London: Chapman & Hall, 1995. xvi + 432 pp.
- Smith T.F., Waterman M.S. Identification of common molecular subsequences // J. Mol. Biol. -1981.-Vol. 147.-P. 195−197.
- Webber С., Barton G.J. Estimation of P-values for global alignments of protein sequences // Bioinformatics. 2001. — Vol. 17, No. 12. — P. 1158−1167.
- Воеводин Вл. В, Жуматий С.А. Вычислительное дело и кластерные системы. М: Изд-во МГУ, 2007. — 150 с.
- Schmid C.D., Perier R., Praz V., Bucher P. EPD in its twentieth year: towards complete promoter coverage of selected model organisms II Nucleic Acids Res. 2006. — Vol. 34. — D82−5.
- Werner T. The state of the art of mammalian promoter recognition // Brief. Bioinform. — 2003. -Vol. 4. No. l.-P. 22−30.
- Fickett J. W., Hatzigeorgiou A.G. Eukaryotic promoter recognition // Genome Res. — 1997. Vol. 7, No. 9.-P. 861−78.