Abstract
Predicting new non-coding RNAs (ncRNAs) of a family can be done by aligning the potential candidate with a member of the family with known sequence and secondary structure. Existing tools either only consider the sequence similarity or cannot handle local alignment with gaps. In this paper, we consider the problem of finding the optimal local structural alignment between a query RNA sequence (with known secondary structure) and a target sequence (with unknown secondary structure) with the affine gap penalty model. We provide the algorithm to solve the problem. Based on a preliminary experiment, we show that there are ncRNA families in which considering local structural alignment with gap penalty model can identify real hits more effectively than using global alignment or local alignment without gap penalty model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Frank, D.N., Pace, N.R.: Ribonuclease p: unity and diversity in a trna processing ribozyme. Annu. Rev. Biochem. 67, 153–180 (1998)
Nguyen, V.T., Kiss, T., Michels, A.A., Bensaude, O.: 7sk small nuclear rna blinds to and inhibits the activity of cdk9/cyclin t complexes. Nature 414, 322–325 (2001)
Wadler, C.S., Vanderpool, C.K.: A dual function for a bacterial small rna: Sgrs performs base pairing-dependent regulation and encodes a functional polypeptide. Proc. Natl. Acad. Sci. USA 104(51), 20454–20459 (2007)
Yang, Z., Zhu, Q., Luo, K., Zhou, Q.: The 7sk small nuclear rna inhibits the cdk9/cyclin t1 kinase to control transcription. Nature 414, 317–322 (2001)
Liu, C., Bai, B., Skogerbo, G., Cai, L., Deng, W., Zhang, Y., Bu, D., Zhao, Y., Chen, R.: Noncode: an integrated knowledge database of non-coding rnas. NAR 33(Database issue), D112–D115 (2005)
Griffiths-Jones, S., Bateman, A., Marshall, M., Khann, A., Eddy, S.R.: Rfam: an rna family database. NAR 31(1), 439–441 (2003), http://www.sanger.ac.uk/Software/Rfam/
Eddy, S.R.: Non-coding rna genes and the modern rna world. Nature Reviews in Genetics 2, 919–929 (2001)
Hertel, J., de Jong, D., Marz, M., Rose, D., Tafer, H., Tanzer, A., Schierwater, B., Stadler, P.F.: Non-coding rna annotation of the genome of trichoplax adhaerens. Nucleic Acids Research 37(5), 1602–1615 (2009)
Klein, R.J., Eddy, S.R.: Rsearch: Finding homologs of single structured rna sequences. BMC Bioinformatics 4(1), 44 (2003)
Zhang, S., Haas, B., Eskin, E., Bafna, V.: Searching genomes for noncoding rna using fastr. IEEE/ACM TCBB 2, 4 (2005)
Tabei, Y., Asai, K.: A local multiple alignment method for detection of non-coding rna sequences. Bioinformatics (2009) doi:10.1093/bioinformatics/btp261
Will, S., Reiche, K., Hofacker, I.L., Stadler, P.F., Backofen, R.: Inferring noncoding rna families and classes by means of genome-scale structure-based clustering. PLOS Computational Biology 3(4), e65 (2007)
Jiang, T., Lin, G., Ma, B., Zhang, K.: A general edit distance between rna structures. Journal of Computational Biology 9(2), 371–388 (2002)
Lin, G.H., Chen, Z.Z., Jiang, T., Wen, J.: The longest common subsequence problem for sequences with nested arc annotations. Journal of Computer and System Sciences 65(3), 465–480 (2002)
Nawrocki, E.P., Eddy, S.R.: Query-dependent banding (qdb) for faster rna similarity searches. PLoS Comput. Biol. 5, e56 (2007)
Le, S., Chen, J., Maizel, J.: Efficient searches for unusual folding regions in rna sequences. In: Structure and Methods: Human Genome Initiative and DNA Recombination, vol. 1, pp. 127–130. Adenine Pr (1990)
Rivas, E., Eddy, S.R.: Secondary structure alone is generally not statistically significant for the detection of noncoding rnas. Bioinformatics 16(7), 583–605 (2000)
Mosig, A., Zhu, L., Stadler, P.F.: Customized strategies for discovering distant ncrna homologs. Briefings in Functional Genomics and Proteomics (2009) (to be appear)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wong, T.K.F., Cheung, B.W.Y., Lam, T.W., Yiu, S.M. (2010). Local Structural Alignment of RNA with Affine Gap Model. In: Borodovsky, M., Gogarten, J.P., Przytycka, T.M., Rajasekaran, S. (eds) Bioinformatics Research and Applications. ISBRA 2010. Lecture Notes in Computer Science(), vol 6053. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13078-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-13078-6_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13077-9
Online ISBN: 978-3-642-13078-6
eBook Packages: Computer ScienceComputer Science (R0)