We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 20 Issue 4
July  2005
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Ying-Lei Song, Ji-Zhen Zhao, Chun-Mei Liu, Kan Liu, Russell Malmberg, Li-Ming Cai. RNA Structural Homology Search with a Succinct Stochastic Grammar Model[J]. Journal of Computer Science and Technology, 2005, 20(4): 454-464.
Citation: Ying-Lei Song, Ji-Zhen Zhao, Chun-Mei Liu, Kan Liu, Russell Malmberg, Li-Ming Cai. RNA Structural Homology Search with a Succinct Stochastic Grammar Model[J]. Journal of Computer Science and Technology, 2005, 20(4): 454-464.
shu

RNA Structural Homology Search with a Succinct Stochastic Grammar Model

  • 1Department of Computer Science, University ofGeorgia, Athens GA30602, U.S.A.
    2Department of Plant Biology, University of Georgia, Athens GA30602,U.S.A.

More Information
  • Revised Date: November 03, 2004
  • Published Date: July 14, 2005
    Abstract
  • An increasing number of structural homology search tools, mostly based on profile stochastic context-free grammars (SCFGs) have been recently developed for the non-coding RNA gene identification. SCFGs can include statistical biases that often occur in RNA sequences, necessary to profile specific RNA structures for structural homology search. In this paper, a succinct stochastic grammar model is introduced for RNA that has competitive search effectiveness. More importantly, the profiling model can be easily extended to include pseudoknots, structures that are beyond the capability of profile SCFGs. In addition, the model allows heuristics to be exploited, resulting in a significant speed-up for the CYK algorithm-based search.
    • FullText(HTML)
    • References (23)
  • [1]
    Sakakibara Y, Brown M, Hughey R et al. Stochastic context-free grammars for tRNA modeling. Nucleic Acids Research, 1994, 22: 5112--5120.
    [2]
    Eddy S R, Durbin R. RNA sequence analysis using covariance models. Nucleic Acids Research, 1994, 22: 2079--2088.
    [3]
    Tinico I, Borer P N, Dengler B et al. Improved estimation of secondary structure in ribonucleic acids.Nature New Biology, 1973, 246: 40--41.
    [4]
    Lowe T M, Eddy S R. tRNAscan-SE: A program for improved detection of transfer RNA genes in genes in genomic sequences. Nucleic Acids Research, 1997, 25: 955--964.
    [5]
    Klein R J, Eddy S R. Rsearch: Finding homologs of single structured RNA sequences.BMC Bioinformatics, 2003, 4(1): 44.
    [6]
    Rivas E, Eddy S R. Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics, 2001, 2(8).
    [7]
    Rivas E, Klein R J, Jones T A, Eddy S R. Computational identification of non-coding RNAs in E. coli by comparative genomics. Curr. Biol., 2001, 1(1): 1369--1373.
    [8]
    Rivas E, Eddy S R. Secondary structure alone is generally not statistically significant for the detection of noncoding RNAs. Bioinformatics, 2000, 16: 583--605.
    [9]
    Eddy S R. Non-coding RNA genes and the modern RNA world. Nature Genetics, 2001, 2: 919--929.
    [10]
    Dowell R D, Eddy S R. Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics, 2004, 5(1): 71.
    [11]
    Knudsen B, Hein J. RNA secondary structure prediction using stochastic context-free grammars and evolutionary history. Bioinformatics, 1999, 15: 446--454.
    [12]
    Durbin R, Eddy S R, Krogh A, Mitchison G J. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids,Cambridge University Press, 1998.
    [13]
    Weinberg Z, Ruzzo W L. Faster genome annotation of non-coding RNA families without loss of accuracy. In Proc.The Eighth Annual Int. Conf. Research in Computational Molecular Biology, 2004, 243--251.
    [14]
    Brown M, Wilson C. RNA pseudoknot modeling using intersections of stochastic context-free grammars with applications to database search. In Pacific Symposium on Biocomputing, 1996.
    [15]
    Felden B, Massire C, Westhof E et al. Phylogenetic analysis of tmRNA genes within a bacterial subgroup reveals a specific structural signature. Nucleic Acids Research, 2001, 29: 1602--1607.
    [16]
    Brown M P. Small subunit ribosomal RNA modeling using stochastic context-free grammars. In Proc. Int. Conf. Intelligent Systems in Molecular Biology, 2000, 8: 57--66.
    [17]
    Holmes I, Rubin D H. Pairwise RNA structure comparison with stochastic context-free grammars. In Pacific Symposium on Biocomputing , 2002, pp.191--203.
    [18]
    Cai L, Malmberg R L, Wu Y. Stochastic modeling of RNA pseudoknotted structures: A grammatical approach. In Proceedings of the 11th Intelligent Systems for Molecular Biology, also Bioinformatics, 2003, 19: 66--73.
    [19]
    Zeenko V V, Ryabova L A, Spirin A S et al. Eukaryotic elongation factor 1A interacts with the upstream pseudoknot domain in the 3' untranslated region of tobacco mosaic virus RNA. Journal of Virology, 2002, 76(11): 5678--5691.
    [20]
    Griffiths-Jones S, Bateman A, Marshall M et al. Rfam: An RNA family database. Nucleic Acids Research, 2003,31(1): 439--441.
    [21]
    Lyngso R B, Pedersen C N S. RNA pseudoknot prediction in energy based models.Journal of Computational Biology, 2000, 7:409--428.
    [22]
    Sprinzl M, Horn C, Brown M et al. Compilation of tRNA sequences and sequences of tRNA genes. Nucleic Acids Research, 1998, 26(1): 148--153.
    [23]
    Tanaka Y, Hori T, Tagaya M et al. Imino proton NMR analysis of HDV ribozymes: Nested double pseudoknot structure and Mg2+ion-binding site close to the catalytic core in solution. Nucleic Acids Research, 2002, 30: 766--774.
    • Relative Articles

  • Related Articles

    [1]Xue-Qi Li, Student, Guang-Ming Tan, Ning-Hui Sun. PIM-Align: A Processing-in-Memory Architecture for FM-Index Search Algorithm[J]. Journal of Computer Science and Technology, 2021, 36(1): 56-70. DOI: 10.1007/s11390-020-0825-3
    [2]Woo-Cheol Kim, Sanghyun Park, Jung-Im Won. CORE: Common Region Extension Based Multiple Protein Structure Alignment for Producing Multiple Solution[J]. Journal of Computer Science and Technology, 2013, 28(4): 647-656. DOI: 10.1007/s11390-013-1365-x
    [3]Xiao-Yong Fang, Zhi-Gang Luo, Zheng-Hua Wang. Predicting RNA Secondary Structure Using Profile Stochastic Context-Free Grammars and Phylogenic Analysis[J]. Journal of Computer Science and Technology, 2008, 23(4): 582-589.
    [4]Guang-Ming Tan, Lin Xu, Dong-Bo Bu, Sheng-Zhong Feng, Ning-Hui Sun. Improvement of Performance of MegaBlast Algorithm for DNA Sequence Alignment[J]. Journal of Computer Science and Technology, 2006, 21(6): 973-978.
    [5]Giuseppe Lancia. Integer Programming Models for Computational Biology Problems[J]. Journal of Computer Science and Technology, 2004, 19(1).
    [6]Giulio Pavesi, Giancarlo Mauri, Graziano Pesole. An Algorithm for Finding Conserved Secondary Structure Motifs in Unaligned RNA Sequences[J]. Journal of Computer Science and Technology, 2004, 19(1).
    [7]WANG Wei, WaNG Yujun, SHI Baile. Dynamic Interval Index Structure in Constraint Database Systems[J]. Journal of Computer Science and Technology, 2000, 15(6): 542-551.
    [8]LING Yu, LI Shu, ZHANG Hui, HAN Chengde. Timing-Sequence Testing of Parallel Programs[J]. Journal of Computer Science and Technology, 2000, 15(1): 84-95.
    [9]CAI Jiamei. The Sequence Modeling Method Based on ECCin Developing Program Specifications[J]. Journal of Computer Science and Technology, 1999, 14(4): 337-348.
    [10]WANG Jian, ZHANG Fuyan. Multicast Address Management and Connection Control Based on Hierarchical Autonomous Structure[J]. Journal of Computer Science and Technology, 1999, 14(1): 64-73.
    • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (17) PDF downloads (1537) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return