{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T11:24:54Z","timestamp":1770981894302,"version":"3.50.1"},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2017,5,5]],"date-time":"2017-05-05T00:00:00Z","timestamp":1493942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Federal Ministry of Education and Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"BMBF","doi-asserted-by":"publisher","award":["031\u20096165A"],"award-info":[{"award-number":["031\u20096165A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004807","name":"DFG","doi-asserted-by":"publisher","award":["BA 2168\/3-3"],"award-info":[{"award-number":["BA 2168\/3-3"]}],"id":[{"id":"10.13039\/100004807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003500","name":"University of Padova","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>The importance of RNA protein-coding gene regulation is by now well appreciated. Non-coding RNAs (ncRNAs) are known to regulate gene expression at practically every stage, ranging from chromatin packaging to mRNA translation. However the functional characterization of specific instances remains a challenging task in genome scale settings. For this reason, automatic annotation approaches are of interest. Existing computational methods are either efficient but non-accurate or they offer increased precision, but present scalability problems.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In this article, we present a predictive system based on kernel methods, a type of machine learning algorithm grounded in statistical learning theory. We employ a flexible graph encoding to preserve multiple structural hypotheses and exploit recent advances in representation and model induction to scale to large data volumes. Experimental results on tens of thousands of ncRNA sequences available from the Rfam database indicate that we can not only improve upon state-of-the-art predictors, but also achieve speedups of several orders of magnitude.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The code is available from http:\/\/www.bioinf.uni-freiburg.de\/~costa\/EDeN.tgz.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btx295","type":"journal-article","created":{"date-parts":[[2017,5,4]],"date-time":"2017-05-04T11:10:22Z","timestamp":1493896222000},"page":"2642-2650","source":"Crossref","is-referenced-by-count":21,"title":["An efficient graph kernel method for non-coding RNA functional prediction"],"prefix":"10.1093","volume":"33","author":[{"given":"Nicol\u00f2","family":"Navarin","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Padova, Padova, Italy"}]},{"given":"Fabrizio","family":"Costa","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Freiburg, Freiburg, Germany"},{"name":"Department of Computer Science, University of Exeter, Exeter, UK"}]}],"member":"286","published-online":{"date-parts":[[2017,5,5]]},"reference":[{"key":"2023020206270349600_btx295-B1","first-page":"917","article-title":"Theoretical foundations of the potential function method in pattern recognition learning","volume":"25","author":"Aizerman","year":"1964","journal-title":"Automat. Remote Contr"},{"key":"2023020206270349600_btx295-B2","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":"2023020206270349600_btx295-B3","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/130385.130401","volume-title":"Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory","author":"Boser","year":"1992"},{"key":"2023020206270349600_btx295-B4","first-page":"177","volume-title":"Proceedings of COMPSTAT\u20192010","author":"Bottou","year":"2010"},{"key":"2023020206270349600_btx295-B5","doi-asserted-by":"crossref","first-page":"D226","DOI":"10.1093\/nar\/gks1005","article-title":"Rfam 11.0: 10\u2009years of RNA families","volume":"41","author":"Burge","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2023020206270349600_btx295-B6","doi-asserted-by":"crossref","first-page":"e66.","DOI":"10.1093\/nar\/gkp206","article-title":"Identification and classification of ncRNA molecules using graph properties","volume":"37","author":"Childs","year":"2009","journal-title":"Nucleic Acids Res"},{"key":"2023020206270349600_btx295-B7","author":"Costa","year":"2010"},{"key":"2023020206270349600_btx295-B8","author":"Da San Martino","year":"2012"},{"key":"2023020206270349600_btx295-B9","author":"Da San Martino","year":"2012"},{"key":"2023020206270349600_btx295-B10","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/j.neucom.2015.12.110","article-title":"Ordered decompositional DAG kernels enhancements","volume":"192","author":"Da San Martino","year":"2016","journal-title":"Neurocomputing"},{"key":"2023020206270349600_btx295-B11","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1073\/pnas.0806929106","article-title":"Accurate shape-directed rna structure determination","volume":"106","author":"Deigan","year":"2009","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020206270349600_btx295-B12","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":"2023020206270349600_btx295-B13","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"MUSCLE: Multiple sequence alignment with high accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020206270349600_btx295-B14","doi-asserted-by":"crossref","first-page":"88.","DOI":"10.1186\/1471-2105-5-88","article-title":"RAG: RNA-As-Graphs web resource","volume":"5","author":"Fera","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023020206270349600_btx295-B15","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.artint.2014.08.003","article-title":"klog: A language for logical and relational learning with kernels","volume":"217","author":"Frasconi","year":"2014","journal-title":"Artif. Intell"},{"key":"2023020206270349600_btx295-B16","doi-asserted-by":"crossref","first-page":"D141","DOI":"10.1093\/nar\/gkq1129","article-title":"Rfam: Wikipedia, clans and the \u201cdecimal\u201d release","volume":"39","author":"Gardner","year":"2011","journal-title":"Nucleic Acids Res"},{"key":"2023020206270349600_btx295-B17","doi-asserted-by":"crossref","first-page":"4843","DOI":"10.1093\/nar\/gkh779","article-title":"Abstract shapes of RNA","volume":"32","author":"Giegerich","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020206270349600_btx295-B18","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","article-title":"Complete suboptimal folding","volume":"49","author":"Hofacker","year":"1999","journal-title":"Biopolymers"},{"key":"2023020206270349600_btx295-B19","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparison of RNA secondary structures","volume":"125","author":"Hofacker","year":"1989","journal-title":"Monatshefte fuer Chemie Chemical Monthly"},{"key":"2023020206270349600_btx295-B20","doi-asserted-by":"crossref","first-page":"5215","DOI":"10.1093\/nar\/gks181","article-title":"Global or local? predicting secondary structure and accessibility in mrnas","volume":"40","author":"Lange","year":"2012","journal-title":"Nucleic Acids Res"},{"key":"2023020206270349600_btx295-B21","first-page":"214","volume-title":"Neural Information Processing of ICONIP, Kyoto, Japan, October 16\u201321, 2016, Part I","author":"Massimo","year":"2016"},{"key":"2023020206270349600_btx295-B22","article-title":"Classification of non-coding RNA using graph representations of secondary structure","author":"Karklin","year":"2005","journal-title":"Pac Symp Biocomput"},{"key":"2023020206270349600_btx295-B23","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1093\/bfgp\/elp035","article-title":"Customized strategies for discovering distant ncRNA homologs","volume":"8","author":"Mosig","year":"2009","journal-title":"Brief. Funct. Genomic. Proteomic"},{"key":"2023020206270349600_btx295-B24","first-page":"1335","article-title":"Infernal 1.0: inference of RNA alignments","volume":"25","author":"Nawrocki","year":"2009","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023020206270349600_btx295-B25","doi-asserted-by":"crossref","first-page":"1929","DOI":"10.1101\/gr.112516.110","article-title":"New families of human regulatory RNA structures identified by comparative analysis of vertebrate genomes","volume":"21","author":"Parker","year":"2011","journal-title":"Genome Res"},{"key":"2023020206270349600_btx295-B26","doi-asserted-by":"crossref","first-page":"1103","DOI":"10.1142\/S0219720007003028","article-title":"Stem kernels for RNA sequence analyses","volume":"5","author":"Sakakibara","year":"2007","journal-title":"J. Bioinformatics Comput. Biol"},{"key":"2023020206270349600_btx295-B27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809682","volume-title":"Kernel Methods for Pattern Analysis","author":"Shawe-Taylor","year":"2004"},{"key":"2023020206270349600_btx295-B28","first-page":"2539","article-title":"Weisfeiler-Lehman graph kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res"},{"key":"2023020206270349600_btx295-B29","first-page":"500","article-title":"RNAshapes: an integrated RNA analysis package based on abstract shapes","volume":"22","author":"Steffen","year":"2006","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023020206270349600_btx295-B30","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1038\/nature14280","article-title":"hiCLIP reveals the in vivo atlas of mRNA secondary structures recognized by Staufen 1","volume":"519","author":"Sugimoto","year":"2015","journal-title":"Nature"},{"key":"2023020206270349600_btx295-B31","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1006\/jmbi.1999.3001","article-title":"How RNA folds","volume":"293","author":"Tinoco","year":"1999","journal-title":"J. Mol. Biol"},{"key":"2023020206270349600_btx295-B32","doi-asserted-by":"crossref","first-page":"80","DOI":"10.2307\/3001968","article-title":"Individual comparisons by ranking methods","volume":"1","author":"Wilcoxon","year":"1945","journal-title":"Biometrics"},{"key":"2023020206270349600_btx295-B33","doi-asserted-by":"crossref","first-page":"1610","DOI":"10.1038\/nprot.2006.249","article-title":"Selective 2\u2032-hydroxyl acylation analyzed by primer extension (SHAPE): quantitative RNA structure analysis at single nucleotide resolution","volume":"1","author":"Wilkinson","year":"2006","journal-title":"Nat. Protoc"},{"key":"2023020206270349600_btx295-B34","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":"2023020206270349600_btx295-B35","doi-asserted-by":"crossref","first-page":"900","DOI":"10.1261\/rna.029041.111","article-title":"LocARNA-P: Accurate boundary prediction and improved detection of structural RNAs","volume":"18","author":"Will","year":"2012","journal-title":"RNA"},{"key":"2023020206270349600_btx295-B36","doi-asserted-by":"crossref","first-page":"1215","DOI":"10.1016\/j.cell.2006.06.009","article-title":"{TUF} love for junk {DNA}","volume":"125","author":"Willingham","year":"2006","journal-title":"Cell"},{"key":"2023020206270349600_btx295-B37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-1-19","article-title":"An enhanced RNA alignment benchmark for sequence alignment programs","volume":"1","author":"Wilm","year":"2006","journal-title":"Algorithms Mol. Biol"},{"key":"2023020206270349600_btx295-B38","doi-asserted-by":"crossref","first-page":"402","DOI":"10.2174\/138920209789177575","article-title":"Hidden Markov models and their applications in biological sequence analysis","volume":"10","author":"Yoon","year":"2009","journal-title":"Curr. Genomics"},{"key":"2023020206270349600_btx295-B39","author":"Zhang","year":"2004"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/17\/2642\/49040804\/bioinformatics_33_17_2642.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/17\/2642\/49040804\/bioinformatics_33_17_2642.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T06:29:22Z","timestamp":1675319362000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/17\/2642\/3798629"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2017,5,5]]},"references-count":39,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2017,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx295","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,9,1]]},"published":{"date-parts":[[2017,5,5]]}}}