Pseudoknots Prediction on RNA Secondary Structure Using Term Rewriting

详细信息    查看全文

• 作者：Linkon Chowdhury (20)
  Mohammad Ibrahim Khan (20)
  
  20. Department of Computer Science and Engineering ; Chittagong University of Engineering and Technology ; Cuet Road ; Zip Code-4349 ; Bangladesh
  
• 关键词：Pseudoknot ; Structure Rewriting (SR) ; Dot Bracket ; Bloom Filter ; Hashing Table
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9043
• 期：1
• 页码：577-588
• 全文大小：699 KB
• 参考文献：1. Batey, R.T., Rambo, R.P., Doudna, J. (1999) Tertiary Motifs in RNA Structure and Folding. Angew. Chem. Int. Ed. Engl. 38: pp. 2326-2343 CrossRef
  2. He, S., Liu, C., Skogerbo, G., Zhao, H., Wang, J., Liu, T., Bai, B., Zhao, Y., Chen, R.: Noncode v2.0: Decoding the Non-Coding. Nucleic Acids Research 36(Database), D170鈥揇172 (2007)
  3. Griffiths-Jones, S., Bateman, A., Marshall, M., Khanna, A., Eddy, S.R. (2003) Rfam: An RNA Family Database. Nucleic Acids Research 31: pp. 439-441 CrossRef
  4. Le, S.Y., Chen, J.H., Maizel, J. (1990) Structure and Methods: Human Genome Initiative and DNA Recombination. Chapter Efficient Searches for Unusual Folding Regions in RNA Sequences 1: pp. 127-130
  5. Rivas, E., Eddy, S. (2000) Secondary Structure Alone is Generally Not Statisti-cally Significant for the Detection of Noncoding RNAs. Bioinformatics 16: pp. 583-605 CrossRef
  6. Thomas, K.F., Wong, Y.S., Chiu, T.W., Lam, S.M. (2012) Memory Efficient Algorithms for Structural Alignment of RNAs with Pseudoknots. IEEE/ACM Transactions on Computational Biology and Bioinformatics 9: pp. 161-168 CrossRef
  7. Hofacker, I.L., Bernhart, S.H.F., Stadler, P.F. (2004) Alignment of RNA base pairing probability matrices. Bioinformatics 20: pp. 2222-2227 CrossRef
  8. Lee, D., Han, K. (2003) Prediction of RNA Pseudoknots 鈥?Comparative Study of Genetic Algorithms. Genome Informatics 13: pp. 414-415
  9. Staple, D.W., Butcher, S.E.: Pseudoknots: RNA Structures with Diverse Functions. PLoS Biology 3(6), e213 (2005)
  10. Pley, H.W., Flaherty, K.M., McKay, D.B.: Threedimensional structure of a hammerhead ribozyme. Nature 372, 68鈥?4 (1994)
  11. Sankoff, D. (1985) Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems. SIAM Journal on Applied Mathematics 45: pp. 810-825 CrossRef
  12. Dowell, R.D., Eddy, S.R.: Efficient pair wise RNA structure prediction and alignment using sequence alignment constraints. BMC Bioinformatics 7(400) (2006)
  13. Holmes, I. (2005) Accelerated probabilistic inference of rna structure evolution. BMC Bioinformatics 6: pp. 73 CrossRef
  14. Knudsen, B., Hein, J. (2003) Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res. 31: pp. 3423-3428 CrossRef
  15. Thompson, J.D., Higgins, D.G., Gibson, T.J. (1994) CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucl. Acids Res. 22: pp. 4673-4680 CrossRef
  16. Blanchette, M., Kent, W.J., Riemer, C., Elnitski, L., Smit, A.F., Roskin, K.M., Baertsch, R., Rosenbloom, K., Clawson, H., Green, E.D., Haussler, D., Miller, W. (2004) Aligning multiple genomic sequences with the threaded blockset aligner. Genome Res. 14: pp. 708-715 CrossRef
  17. Mccaskill, S. (1990) The equilibrium partition function and base pair binding probabilities for rna secondarystructure. Biopolymers 29: pp. 1105-1119 CrossRef
  18. Torarinsson, E., Havgaard, J.H., Gorodkin, J. (2007) Multiple structural align-ment and clustering of RNA sequences. Bioinformatics 23: pp. 926-932 CrossRef
  19. Washietl, S., Hofacker, I.L., Stadler, P.F. (2005) Fast and reliable prediction of noncoding RNAs. Proc. Natl. Acad. Sci. U S A 102: pp. 2454-2459 CrossRef
  20. Hochsmann, M., Voss, B., Giegerich, R. (2004) Pure multiple RNA secondary structure alignments: a progressive profile approach. IEEE/ACM Trans. Comput. Biol. Bioinform. 1: pp. 53-62 CrossRef
  21. Touzet, H., Perriquet, O.: CARNAC:folding families of related RNAs. Nucl. Acids Res. 32(suppl. 2), W142鈥揥145 (2004)
  22. Bloom, B.: Space/time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM 13(7), 422鈥?26
  23. Eker, S.: Fast matching in combination of regular equational theories. In: Meseguer, J. (ed.) Proceedings First International Workshop on Rewriting Logic and its Applications. Electronic Notes in Theoretical Computer Science, vol. 4, pp. 90鈥?09. Elsevier (1996)
  24. Zuker, M. (2003) Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Research 31: pp. 3406-3415 CrossRef
  25. Rouzina, I., Bloomfield, V.A.: Heat Capacity Effects on the Melting of DNA.2. Analysis of Nearest-Neighbor Base Pair Effects. Biophysical Journal 77(6), 3252鈥?255 (1999)
  26. Bloom, B.H. (1970) Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13: pp. 422-426 CrossRef
  27. Tabaska, J., Cary, R., Gabow, H., Stormo, G. (1998) An RNA folding method capable of identifying pseudoknots and base triples. Bioinformatics 14: pp. 691-699 CrossRef
  28. Ruan, J., Stormo, G.D., Zhang, W. (2004) An Iterated loop matching approach to the prediction of RNA secondary structures with Pseudoknots. Bioinformatics 20: pp. 58-66 CrossRef
  
• 作者单位：Bioinformatics and Biomedical Engineering
• 丛书名：978-3-319-16482-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

The presences of Pseudoknots generate computational complexities during RNA (Ribonucleic Acid) secondary structure analysis. It is a well known NP hard problem in computational system. It is very essential to have an automated algorithm based system to predict the Pseudoknots from billions of data set. RNA plays a vital role in meditation of cellular information transfer from genes to functional proteins. Pseudoknots are seldom repeated forms that produce misleading computational cost and memory. Memory reducing under bloom filter proposes a memory efficient algorithm for prediction Pseudoknot of RNA secondary structure. RNA Pseudoknot structure prediction based on bloom filter rather than dynamic programming and context free grammar. At first, Structure Rewriting (SR) technique is used to represent secondary structure. Secondary structure is represented in dot bracket representation. Represented secondary structure is separated into two portions to reduce structural complexity. Dot bracket is placed into bloom filter for finding Pseudoknot. In bloom filter, hashing table is used to occupy the RNA based nucleotide. Our proposed algorithm experiences on 105 Pseudoknots in pseudobase and achieves accuracy 66.159% to determine structure.