{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T06:40:12Z","timestamp":1761892812796},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"10","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2753,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,5,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Accuracy of automated structural RNA alignment is improved by using models that consider not only primary sequence but also secondary structure information. However, current RNA structural alignment approaches tend to perform poorly on incomplete sequence fragments, such as single reads from metagenomic environmental surveys, because nucleotides that are expected to be base paired are missing.<\/jats:p>\n               <jats:p>Results: We present a local RNA structural alignment algorithm, trCYK, for aligning and scoring incomplete sequences under a model using primary sequence conservation and secondary structure information when possible. The trCYK algorithm improves alignment accuracy and coverage of sequence fragments of structural RNAs in simulated metagenomic shotgun datasets.<\/jats:p>\n               <jats:p>Availability: The source code for Infernal 1.0, which includes trCYK, is available at http:\/\/infernal.janelia.org<\/jats:p>\n               <jats:p>Contact: \u00a0kolbed@janelia.hhmi.org; eddys@janelia.hhmi.org<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp154","type":"journal-article","created":{"date-parts":[[2009,3,21]],"date-time":"2009-03-21T01:29:56Z","timestamp":1237598996000},"page":"1236-1243","source":"Crossref","is-referenced-by-count":16,"title":["Local RNA structure alignment with incomplete sequence"],"prefix":"10.1093","volume":"25","author":[{"given":"Diana L.","family":"Kolbe","sequence":"first","affiliation":[{"name":"HHMI Janelia Farm Research Campus, Ashburn VA 20147, USA"}]},{"given":"Sean R.","family":"Eddy","sequence":"additional","affiliation":[{"name":"HHMI Janelia Farm Research Campus, Ashburn VA 20147, USA"}]}],"member":"286","published-online":{"date-parts":[[2009,3,20]]},"reference":[{"key":"2023013110292051600_B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023013110292051600_B2","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023013110292051600_B3","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1142\/S0219720004000818","article-title":"Local sequence-structure motifs in RNA","volume":"2","author":"Backofen","year":"2004","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023013110292051600_B4","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1093\/nar\/27.1.314","article-title":"The ribonuclease P database","volume":"27","author":"Brown","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023013110292051600_B5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1186\/1471-2105-3-2","article-title":"The Comparative RNA Web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs","volume":"3","author":"Cannone","year":"2002","journal-title":"BMC Bioinformatics."},{"key":"2023013110292051600_B6","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1371\/journal.pcbi.0010024","article-title":"Bioinformatics for whole-genome shotgun sequencing of microbial communities","volume":"1","author":"Chen","year":"2005","journal-title":"PLoS Comput. Biol."},{"key":"2023013110292051600_B7","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1002\/j.1460-2075.1986.tb04288.x","article-title":"The relation between the divergence of sequence and structure in proteins","volume":"5","author":"Chothia","year":"1986","journal-title":"EMBO J."},{"key":"2023013110292051600_B8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids.","author":"Durbin","year":"1998"},{"key":"2023013110292051600_B9","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1186\/1471-2105-3-18","article-title":"A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure","volume":"3","author":"Eddy","year":"2002","journal-title":"BMC Bioinformatics"},{"key":"2023013110292051600_B10","author":"Eddy","year":"2008","journal-title":"HMMER - biosequence analysis using profile hidden Markov models."},{"key":"2023013110292051600_B11","doi-asserted-by":"crossref","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","article-title":"RNA sequence analysis using covariance models","volume":"22","author":"Eddy","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023013110292051600_B12","doi-asserted-by":"crossref","first-page":"D136","DOI":"10.1093\/nar\/gkn766","article-title":"Rfam: updates to the RNA families database","volume":"37","author":"Gardner","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"2023013110292051600_B13","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/S0959-440X(96)80058-3","article-title":"Surprising similarities in structure comparison","volume":"6","author":"Gibrat","year":"1996","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023013110292051600_B14","doi-asserted-by":"crossref","first-page":"D121","DOI":"10.1093\/nar\/gki081","article-title":"Rfam: annotating non-coding RNAs in complete genomes","volume":"33","author":"Griffiths-Jones","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023013110292051600_B15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology.","author":"Gusfield","year":"1997"},{"key":"2023013110292051600_B16","volume-title":"Introduction to Automata Theory, Languages, and Computation.","author":"Hopcroft","year":"1979"},{"key":"2023013110292051600_B17","article-title":"An efficient recognition and syntax algorithm for context-free algorithms","volume-title":"Technical Report AFCRL-65-758.","author":"Kasami","year":"1965"},{"key":"2023013110292051600_B18","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1186\/1471-2105-4-44","article-title":"RSEARCH: finding homologs of single structured RNA sequences","volume":"4","author":"Klein","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023013110292051600_B19","doi-asserted-by":"crossref","first-page":"e56","DOI":"10.1371\/journal.pcbi.0030056","article-title":"Query-dependent banding (QDB) for faster RNA similarity searches","volume":"3","author":"Nawrocki","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023013110292051600_B20","doi-asserted-by":"crossref","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","article-title":"Improved tools for biological sequence comparison","volume":"85","author":"Pearson","year":"1988","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013110292051600_B21","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1093\/biomet\/63.3.581","article-title":"Inference and missing data","volume":"63","author":"Rubin","year":"1976","journal-title":"Biometrika"},{"key":"2023013110292051600_B22","doi-asserted-by":"crossref","first-page":"e77","DOI":"10.1371\/journal.pbio.0050077","article-title":"The sorcerer II global ocean sampling expedition: northwest Atlantic through eastern tropical Pacific","volume":"5","author":"Rusch","year":"2007","journal-title":"PLoS Biol."},{"key":"2023013110292051600_B23","doi-asserted-by":"crossref","first-page":"5112","DOI":"10.1093\/nar\/22.23.5112","article-title":"Stochastic context-free grammars for tRNA modeling","volume":"22","author":"Sakakibara","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"2023013110292051600_B24","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1186\/gb-2005-6-8-229","article-title":"Metagenomics for studying unculturable microorganisms: cutting the gordian knot","volume":"6","author":"Schloss","year":"2005","journal-title":"Genome Biol."},{"key":"2023013110292051600_B25","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"2023013110292051600_B26","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1126\/science.1093857","article-title":"Environmental genome shotgun sequencing of the Sargasso Sea","volume":"304","author":"Venter","year":"2004","journal-title":"Science"},{"key":"2023013110292051600_B27","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/j.sbi.2004.03.011","article-title":"Structure, function and evolution of multidomain proteins","volume":"14","author":"Vogel","year":"2004","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023013110292051600_B28","doi-asserted-by":"crossref","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","article-title":"Inferring noncoding RNA families and classes by means of genome-scale structure-based clustering","volume":"3","author":"Will","year":"2007","journal-title":"PLoS Comput Biol."},{"key":"2023013110292051600_B29","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1093\/bioinformatics\/btk008","article-title":"CMfinder\u2013a covariance model based RNA motif finding algorithm","volume":"22","author":"Yao","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013110292051600_B30","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","article-title":"Recognition and parsing of context-free languages in time n3","volume":"10","author":"Younger","year":"1967","journal-title":"Inform. Control"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/10\/1236\/48990052\/bioinformatics_25_10_1236.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/10\/1236\/48990052\/bioinformatics_25_10_1236.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T20:38:12Z","timestamp":1675197492000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/10\/1236\/270551"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,20]]},"references-count":30,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2009,5,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp154","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,5,15]]},"published":{"date-parts":[[2009,3,20]]}}}