{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T19:13:41Z","timestamp":1761765221123,"version":"3.37.0"},"reference-count":52,"publisher":"Oxford University Press (OUP)","issue":"22","license":[{"start":{"date-parts":[[2016,10,1]],"date-time":"2016-10-01T00:00:00Z","timestamp":1475280000000},"content-version":"vor","delay-in-days":2578,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,11,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: The computational identification of non-coding RNA (ncRNA) genes represents one of the most important and challenging problems in computational biology. Existing methods for ncRNA gene prediction rely mostly on homology information, thus limiting their applications to ncRNA genes with known homologues.<\/jats:p><jats:p>Results: We present a novel de novo prediction algorithm for ncRNA genes using features derived from the sequences and structures of known ncRNA genes in comparison to decoys. Using these features, we have trained a neural network-based classifier and have applied it to Escherichia coli and Sulfolobus solfataricus for genome-wide prediction of ncRNAs. Our method has an average prediction sensitivity and specificity of 68% and 70%, respectively, for identifying windows with potential for ncRNA genes in E.coli. By combining windows of different sizes and using positional filtering strategies, we predicted 601 candidate ncRNAs and recovered 41% of known ncRNAs in E.coli. We experimentally investigated six novel candidates using Northern blot analysis and found expression of three candidates: one represents a potential new ncRNA, one is associated with stable mRNA decay intermediates and one is a case of either a potential riboswitch or transcription attenuator involved in the regulation of cell division. In general, our approach enables the identification of both cis- and trans-acting ncRNAs in partially or completely sequenced microbial genomes without requiring homology or structural conservation.<\/jats:p><jats:p>Availability: The source code and results are available at http:\/\/csbl.bmb.uga.edu\/publications\/materials\/tran\/.<\/jats:p><jats:p>Contact: \u00a0xyn@bmb.uga.edu<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp537","type":"journal-article","created":{"date-parts":[[2009,9,11]],"date-time":"2009-09-11T00:34:34Z","timestamp":1252629274000},"page":"2897-2905","source":"Crossref","is-referenced-by-count":35,"title":["<i>De novo<\/i>computational prediction of non-coding RNA genes in prokaryotic genomes"],"prefix":"10.1093","volume":"25","author":[{"given":"Thao T.","family":"Tran","sequence":"first","affiliation":[{"name":"1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, 2Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, Institute of Bioinformatics and BioEnergy Science Center (BESC), 3Department of Genetics, University of Georgia, Athens, GA, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China"},{"name":"1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, 2Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, Institute of Bioinformatics and BioEnergy Science Center (BESC), 3Department of Genetics, University of Georgia, Athens, GA, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fengfeng","family":"Zhou","sequence":"additional","affiliation":[{"name":"1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, 2Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, Institute of Bioinformatics and BioEnergy Science Center (BESC), 3Department of Genetics, University of Georgia, Athens, GA, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarah","family":"Marshburn","sequence":"additional","affiliation":[{"name":"1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, 2Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, Institute of Bioinformatics and BioEnergy Science Center (BESC), 3Department of Genetics, University of Georgia, Athens, GA, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Stead","sequence":"additional","affiliation":[{"name":"1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, 2Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, Institute of Bioinformatics and BioEnergy Science Center (BESC), 3Department of Genetics, University of Georgia, Athens, GA, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sidney R.","family":"Kushner","sequence":"additional","affiliation":[{"name":"1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, 2Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, Institute of Bioinformatics and BioEnergy Science Center (BESC), 3Department of Genetics, University of Georgia, Athens, GA, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Xu","sequence":"additional","affiliation":[{"name":"1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, 2Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, Institute of Bioinformatics and BioEnergy Science Center (BESC), 3Department of Genetics, University of Georgia, Athens, GA, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China"},{"name":"1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, 2Computational Systems Biology Laboratory, Department of Biochemistry and Molecular Biology, Institute of Bioinformatics and BioEnergy Science Center (BESC), 3Department of Genetics, University of Georgia, Athens, GA, USA and 4College of Computer Science and Technology, Jilin University, Changchun, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2009,9,10]]},"reference":[{"key":"2023013112154527700_B1","first-page":"526","article-title":"Significance of nucleotide sequence alignments: a method for random sequence permutation that preserves dinucleotide and codon usage","volume":"2","author":"Altschul","year":"1985","journal-title":"Mol. Biol. Evol."},{"key":"2023013112154527700_B2","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1016\/S0960-9822(01)00270-6","article-title":"Novel small RNA-encoding genes in the intergenic regions","volume":"11","author":"Argaman","year":"2001","journal-title":"Escherichia coli. Curr. Biol."},{"key":"2023013112154527700_B3","doi-asserted-by":"crossref","first-page":"2758","DOI":"10.1073\/pnas.0308747101","article-title":"Global analysis of Escherichia coli RNA degradosome function using DNA microarrays","volume":"101","author":"Bernstein","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112154527700_B4","doi-asserted-by":"crossref","first-page":"3928","DOI":"10.1093\/nar\/29.19.3928","article-title":"A computational approach to identify genes for functional RNAs in genomic sequences","volume":"29","author":"Carter","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00285-007-0129-z","article-title":"Boltzmann ensemble features of RNA secondary structures: a comparative analysis of biological RNA sequences and random shuffles","volume":"56","author":"Chan","year":"2008","journal-title":"J. Math. Biol."},{"key":"2023013112154527700_B6","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/S0303-2647(02)00013-8","article-title":"A bioinformatics based approach to discover small RNA genes in the Escherichia coli genome","volume":"65","author":"Chen","year":"2002","journal-title":"Biosystems"},{"key":"2023013112154527700_B7","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1261\/rna.7220505","article-title":"Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency","volume":"11","author":"Clote","year":"2005","journal-title":"Rna"},{"key":"2023013112154527700_B8","doi-asserted-by":"crossref","first-page":"12102","DOI":"10.1073\/pnas.0404193101","article-title":"MSARI: multiple sequence alignments for statistical detection of RNA secondary structure","volume":"101","author":"Coventry","year":"2004","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112154527700_B9","doi-asserted-by":"crossref","first-page":"1606","DOI":"10.1093\/bioinformatics\/btg229","article-title":"ddbRNA: detection of conserved secondary structures in multiple alignments","volume":"19","author":"di Bernardo","year":"2003","journal-title":"Bioinformatics"},{"key":"2023013112154527700_B10","doi-asserted-by":"crossref","first-page":"7280","DOI":"10.1093\/nar\/gkg938","article-title":"A statistical sampling algorithm for RNA secondary structure prediction","volume":"31","author":"Ding","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B11","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1261\/rna.2500605","article-title":"RNA secondary structure prediction by centroids in a Boltzmann weighted ensemble","volume":"11","author":"Ding","year":"2005","journal-title":"Rna"},{"key":"2023013112154527700_B12","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1016\/j.jmb.2006.01.056","article-title":"Clustering of RNA secondary structures with application to messenger RNAs","volume":"359","author":"Ding","year":"2006","journal-title":"J. Mol. Biol."},{"key":"2023013112154527700_B13","doi-asserted-by":"crossref","first-page":"1457","DOI":"10.1038\/nbt1104-1457","article-title":"How do RNA folding algorithms work?","volume":"22","author":"Eddy","year":"2004","journal-title":"Nat. Biotechnol."},{"key":"2023013112154527700_B14","doi-asserted-by":"crossref","first-page":"1575","DOI":"10.1093\/nar\/30.7.1575","article-title":"An efficient algorithm for large-scale detection of protein families","volume":"30","author":"Enright","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B15","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1186\/1471-2105-6-241","article-title":"A comparison of RNA folding measures","volume":"6","author":"Freyhult","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023013112154527700_B16","doi-asserted-by":"crossref","first-page":"895","DOI":"10.1006\/jmbi.2000.3593","article-title":"Archaeal homologs of eukaryotic methylation guide small nucleolar RNAs: lessons from the Pyrococcus genomes","volume":"297","author":"Gaspin","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023013112154527700_B17","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/j.tig.2005.05.008","article-title":"Micros for microbes: non-coding regulatory RNAs in bacteria","volume":"21","author":"Gottesman","year":"2005","journal-title":"Trends Genet."},{"key":"2023013112154527700_B18","doi-asserted-by":"crossref","first-page":"W70","DOI":"10.1093\/nar\/gkn188","article-title":"The Vienna RNA websuite","volume":"36","author":"Gruber","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B19","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1093\/nar\/gkj469","article-title":"Experimental approaches to identify non-coding RNAs","volume":"34","author":"Huttenhofer","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B20","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1016\/S1367-5931(02)00397-6","article-title":"RNomics: identification and function of small, non-messenger RNAs","volume":"6","author":"Huttenhofer","year":"2002","journal-title":"Curr. Opin. Chem. Biol."},{"key":"2023013112154527700_B21","doi-asserted-by":"crossref","first-page":"1104","DOI":"10.1006\/jmbi.1997.0889","article-title":"Assessing the reliability of RNA folding using statistical mechanics","volume":"267","author":"Huynen","year":"1997","journal-title":"J. Mol. Biol."},{"key":"2023013112154527700_B22","doi-asserted-by":"crossref","first-page":"3077","DOI":"10.1002\/j.1460-2075.1994.tb06606.x","article-title":"Mechanism of the down-regulation of cAMP receptor protein by glucose in Escherichia coli : role of autoregulation of the crp gene","volume":"13","author":"Ishizuka","year":"1994","journal-title":"EMBO J."},{"key":"2023013112154527700_B23","doi-asserted-by":"crossref","first-page":"7706","DOI":"10.1073\/pnas.86.20.7706","article-title":"Improved predictions of secondary structures for RNA","volume":"86","author":"Jaeger","year":"1989","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023013112154527700_B24","doi-asserted-by":"crossref","first-page":"R22","DOI":"10.1186\/gb-2007-8-2-r22","article-title":"Rapid, accurate, computational discovery of Rho-independent transcription terminators illuminates their relationship to DNA uptake","volume":"8","author":"Kingsford","year":"2007","journal-title":"Genome Biol."},{"key":"2023013112154527700_B25","doi-asserted-by":"crossref","first-page":"7542","DOI":"10.1073\/pnas.112063799","article-title":"Noncoding RNA genes identified in AT-rich hyperthermophiles","volume":"99","author":"Klein","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112154527700_B26","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1101\/gr.069104.107","article-title":"De novo search for non-coding RNA genes in the AT-rich genome of Dictyostelium discoideum: performance of Markov-dependent genome feature scoring","volume":"18","author":"Larsson","year":"2008","journal-title":"Genome Res."},{"key":"2023013112154527700_B27","doi-asserted-by":"crossref","first-page":"D112","DOI":"10.1093\/nar\/gki041","article-title":"NONCODE: an integrated knowledge database of non-coding RNAs","volume":"33","author":"Liu","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B28","doi-asserted-by":"crossref","first-page":"e29","DOI":"10.1371\/journal.pgen.0020029","article-title":"Distinguishing protein-coding from non-coding RNAs through support vector machines","volume":"2","author":"Liu","year":"2006","journal-title":"PLoS Genet."},{"key":"2023013112154527700_B29","doi-asserted-by":"crossref","first-page":"1517","DOI":"10.1002\/jcc.20911","article-title":"RNACluster: An integrated tool for RNA secondary structure comparison and clustering","volume":"29","author":"Liu","year":"2008","journal-title":"J. Comput. Chem."},{"key":"2023013112154527700_B30","doi-asserted-by":"crossref","first-page":"4096","DOI":"10.1093\/nar\/gki715","article-title":"sRNAPredict: an integrative computational approach to identify sRNAs in bacterial genomes","volume":"33","author":"Livny","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B31","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1093\/nar\/gkm991","article-title":"Rho-independent transcription terminators inhibit RNase P processing of the secG leuU and metT tRNA polycistronic transcripts in Escherichia coli","volume":"36","author":"Mohanty","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B32","doi-asserted-by":"crossref","first-page":"1807","DOI":"10.1073\/pnas.92.6.1807","article-title":"Polyadenylylation helps regulate mRNA decay in Escherichia coli","volume":"92","author":"O'Hara","year":"1995","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112154527700_B33","doi-asserted-by":"crossref","first-page":"1102","DOI":"10.1101\/gad.983502","article-title":"Initiation of tRNA maturation by RNase E is essential for cell viability in E. coli","volume":"16","author":"Ow","year":"2002","journal-title":"Genes Dev."},{"key":"2023013112154527700_B34","doi-asserted-by":"crossref","first-page":"e33","DOI":"10.1371\/journal.pcbi.0020033","article-title":"Identification and classification of conserved RNA secondary structures in the human genome","volume":"2","author":"Pedersen","year":"2006","journal-title":"PLoS Comput Biol."},{"key":"2023013112154527700_B35","doi-asserted-by":"crossref","first-page":"1707","DOI":"10.1093\/bioinformatics\/btg235","article-title":"Intergenic sequence inspector: searching and identifying bacterial RNAs","volume":"19","author":"Pichon","year":"2003","journal-title":"Bioinformatics"},{"key":"2023013112154527700_B36","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1093\/bioinformatics\/16.7.583","article-title":"Secondary structure alone is generally not statistically significant for the detection of noncoding RNAs","volume":"16","author":"Rivas","year":"2000","journal-title":"Bioinformatics"},{"key":"2023013112154527700_B37","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1471-2105-2-8","article-title":"Noncoding RNA gene detection using comparative sequence analysis","volume":"2","author":"Rivas","year":"2001","journal-title":"BMC Bioinformatics"},{"key":"2023013112154527700_B38","doi-asserted-by":"crossref","first-page":"1369","DOI":"10.1016\/S0960-9822(01)00401-8","article-title":"Computational identification of noncoding RNAs in E. coli by comparative genomics","volume":"11","author":"Rivas","year":"2001","journal-title":"Curr. Biol."},{"key":"2023013112154527700_B39","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1016\/S0923-2508(99)00126-6","article-title":"Novel intergenic repeats of Escherichia coli K-12","volume":"150","author":"Rudd","year":"1999","journal-title":"Res. Microbiol."},{"key":"2023013112154527700_B40","doi-asserted-by":"crossref","first-page":"3263","DOI":"10.1093\/nar\/gki644","article-title":"Predicting non-coding RNA genes in Escherichia coli with boosted genetic programming","volume":"33","author":"Saetrom","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B41","doi-asserted-by":"crossref","first-page":"2076","DOI":"10.1093\/nar\/30.9.2076","article-title":"Searching for RNA genes using base-composition statistics","volume":"30","author":"Schattner","year":"2002","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B42","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1111\/j.1365-2958.2005.04841.x","article-title":"The MreB and Min cytoskeletal-like systems play independent roles in prokaryotic polar differentiation","volume":"58","author":"Shih","year":"2005","journal-title":"Mol. Microbiol."},{"key":"2023013112154527700_B43","first-page":"1","article-title":"Noncoding RNA transcripts","volume":"44","author":"Szymanski","year":"2003","journal-title":"J. Appl. Genet."},{"key":"2023013112154527700_B44","doi-asserted-by":"crossref","first-page":"2791","DOI":"10.1093\/nar\/gkl356","article-title":"Target prediction for small, noncoding RNAs in bacteria","volume":"34","author":"Tjaden","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B45","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1093\/nar\/gkl974","article-title":"Operon prediction in Pyrococcus furiosus","volume":"35","author":"Tran","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B46","doi-asserted-by":"crossref","first-page":"2712","DOI":"10.1271\/bbb.60315","article-title":"Transcriptional analysis of the Escherichia coli mreBCD genes responsible for morphogenesis and chromosome segregation","volume":"70","author":"Wachi","year":"2006","journal-title":"Biosci. Biotechnol. Biochem."},{"key":"2023013112154527700_B47","doi-asserted-by":"crossref","first-page":"2590","DOI":"10.1093\/bioinformatics\/btl441","article-title":"PSoL: a positive sample only learning algorithm for finding non-coding RNA genes","volume":"22","author":"Wang","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013112154527700_B48","doi-asserted-by":"crossref","first-page":"2454","DOI":"10.1073\/pnas.0409169102","article-title":"Fast and reliable prediction of noncoding RNAs","volume":"102","author":"Washietl","year":"2005","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023013112154527700_B49","doi-asserted-by":"crossref","first-page":"1637","DOI":"10.1101\/gad.901001","article-title":"Identification of novel small RNAs using comparative genomics and microarrays","volume":"15","author":"Wassarman","year":"2001","journal-title":"Genes Dev."},{"key":"2023013112154527700_B50","doi-asserted-by":"crossref","first-page":"4816","DOI":"10.1093\/nar\/27.24.4816","article-title":"No evidence that mRNAs have lower folding free energies than random sequences with the same dinucleotide distribution","volume":"27","author":"Workman","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023013112154527700_B51","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.gene.2005.12.034","article-title":"Prediction of non-coding and antisense RNA genes in Escherichia coli with Gapped Markov Model","volume":"372","author":"Yachie","year":"2006","journal-title":"Gene"},{"key":"2023013112154527700_B52","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1093\/bioinformatics\/btg457","article-title":"Conservation analysis of small RNA genes in Escherichia coli","volume":"20","author":"Zhang","year":"2004","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/22\/2897\/48997638\/bioinformatics_25_22_2897.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/22\/2897\/48997638\/bioinformatics_25_22_2897.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T03:03:07Z","timestamp":1739329387000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/22\/2897\/180485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,10]]},"references-count":52,"journal-issue":{"issue":"22","published-print":{"date-parts":[[2009,11,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp537","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"type":"electronic","value":"1367-4811"},{"type":"print","value":"1367-4803"}],"subject":[],"published-other":{"date-parts":[[2009,11,15]]},"published":{"date-parts":[[2009,9,10]]}}}