{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:45:38Z","timestamp":1740185138442,"version":"3.37.3"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"vor","delay-in-days":12,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100004807","name":"DFG","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004807","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Germany\u2019s Excellence Strategy","award":["390939984","BA 2168\/14-1","BA 2168\/3-3"],"award-info":[{"award-number":["390939984","BA 2168\/14-1","BA 2168\/3-3"]}]},{"name":"German Federal Ministry of Education and Research"},{"DOI":"10.13039\/501100002347","name":"BMBF","doi-asserted-by":"publisher","award":["031A538A"],"award-info":[{"award-number":["031A538A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Elucidating the functions of non-coding RNAs by homology has been strongly limited due to fundamental computational and modeling issues. While existing simultaneous alignment and folding (SA&amp;F) algorithms successfully align homologous RNAs with precisely known boundaries (global SA&amp;F), the more pressing problem of identifying new classes of homologous RNAs in the genome (local SA&amp;F) is intrinsically more difficult and much less understood. Typically, the length of local alignments is strongly overestimated and alignment boundaries are dramatically mispredicted. We hypothesize that local SA&amp;F approaches are compromised this way due to a score bias, which is caused by the contribution of RNA structure similarity to their overall alignment score.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In the light of this hypothesis, we study pairwise local SA&amp;F for the first time systematically\u2014based on a novel local RNA alignment benchmark set and quality measure. First, we vary the relative influence of structure similarity compared to sequence similarity. Putting more emphasis on the structure component leads to overestimating the length of local alignments. This clearly shows the bias of current scores and strongly hints at the structure component as its origin. Second, we study the interplay of several important scoring parameters by learning parameters for local and global SA&amp;F. The divergence of these optimized parameter sets underlines the fundamental obstacles for local SA&amp;F. Third, by introducing a position-wise correction term in local SA&amp;F, we constructively solve its principal issues.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The benchmark data, detailed results and scripts are available at https:\/\/github.com\/BackofenLab\/local_alignment. The RNA alignment tool LocARNA, including the modifications proposed in this work, is available at https:\/\/github.com\/s-will\/LocARNA\/releases\/tag\/v2.0.0RC6.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa431","type":"journal-article","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T19:18:10Z","timestamp":1588792690000},"page":"i242-i250","source":"Crossref","is-referenced-by-count":0,"title":["The locality dilemma of Sankoff-like RNA alignments"],"prefix":"10.1093","volume":"36","author":[{"given":"Teresa","family":"M\u00fcller","sequence":"first","affiliation":[{"name":"Bioinformatics Group, University of Freiburg , Freiburg 79110, Germany"}]},{"given":"Milad","family":"Miladi","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, University of Freiburg , Freiburg 79110, Germany"}]},{"given":"Frank","family":"Hutter","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Freiburg Machine Learning Lab, , Freiburg 79110, Germany"}]},{"given":"Ivo","family":"Hofacker","sequence":"additional","affiliation":[{"name":"Theoretical Biochemistry Group (TBI), Institute for Theoretical Chemistry, University of Vienna , Vienna, Wien 1090, Austria"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[{"name":"Theoretical Biochemistry Group (TBI), Institute for Theoretical Chemistry, University of Vienna , Vienna, Wien 1090, Austria"},{"name":"Bioinformatics Group AMIBio, LIX\u2014Laboratoire d\u2019Informatique d\u2019\u00c9cole Polytechnique, IPP , Palaiseau 91120, France"}]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, University of Freiburg , Freiburg 79110, Germany"},{"name":"Signalling Research Centres BIOSS and CIBSS, University of Freiburg , Freiburg 79104, Germany"}]}],"member":"286","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"key":"2024021913335906200_btaa431-B1","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/0022-2836(91)90193-A","article-title":"Amino acid substitution matrices from an information theoretic perspective","volume":"219","author":"Altschul","year":"1991","journal-title":"J. Mol. Biol"},{"key":"2024021913335906200_btaa431-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":"2024021913335906200_btaa431-B3","doi-asserted-by":"crossref","first-page":"W202","DOI":"10.1093\/nar\/gkp335","article-title":"Meme suite: tools for motif discovery and searching","volume":"37","author":"Bailey","year":"2009","journal-title":"Nucleic Acids Res"},{"key":"2024021913335906200_btaa431-B4","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/nar\/gki541","article-title":"A benchmark of multiple sequence alignment programs upon structural RNAs","volume":"33","author":"Gardner","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2024021913335906200_btaa431-B5","doi-asserted-by":"crossref","first-page":"2135","DOI":"10.1093\/nar\/29.10.2135","article-title":"Discovering common stem\u2013loop motifs in unaligned RNA sequences","volume":"29","author":"Gorodkin","year":"2001","journal-title":"Nucleic Acids Res"},{"key":"2024021913335906200_btaa431-B6","first-page":"69","article-title":"RNAZ 2.0: improved noncoding RNA detection","volume":"15","author":"Gruber","year":"2010","journal-title":"Pac. Symp. Biocomput"},{"key":"2024021913335906200_btaa431-B7","doi-asserted-by":"crossref","first-page":"W650","DOI":"10.1093\/nar\/gki473","article-title":"The foldalign web server for pairwise structural RNA alignment and mutual motif search","volume":"33","author":"Havgaard","year":"2005","journal-title":"Nucleic Acids Res"},{"key":"2024021913335906200_btaa431-B8","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1023\/A:1010085313469","article-title":"A generalized Erd\u00f6s-R\u00e9ny law for sequence analysis problems","volume":"2","author":"Heyer","year":"2000","journal-title":"Methodol. Comput. Appl. Prob"},{"key":"2024021913335906200_btaa431-B9","doi-asserted-by":"crossref","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","article-title":"Alignment of RNA base pairing probability matrices","volume":"20","author":"Hofacker","year":"2004","journal-title":"Bioinformatics"},{"key":"2024021913335906200_btaa431-B10","doi-asserted-by":"crossref","first-page":"D84","DOI":"10.1093\/nar\/gky1078","article-title":"The European nucleotide archive in 2018","volume":"47","author":"Hussein","year":"2019","journal-title":"Nucleic Acids Res"},{"first-page":"507","year":"2011","author":"Hutter","key":"2024021913335906200_btaa431-B11"},{"key":"2024021913335906200_btaa431-B12","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1186\/1471-2105-9-192","article-title":"ushuffle: a useful tool for shuffling biological sequences while preserving the k-let counts","volume":"9","author":"Jiang","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2024021913335906200_btaa431-B13","doi-asserted-by":"crossref","first-page":"2264","DOI":"10.1073\/pnas.87.6.2264","article-title":"Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes","volume":"87","author":"Karlin","year":"1990","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2024021913335906200_btaa431-B14","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1214\/aos\/1176347616","article-title":"Statistical composition of high-scoring segments from molecular sequences","volume":"18","author":"Karlin","year":"1990","journal-title":"Ann. Stat"},{"key":"2024021913335906200_btaa431-B15","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":"2024021913335906200_btaa431-B16","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1006\/jmbi.2001.5351","article-title":"Dynalign: an algorithm for finding the secondary structure common to two RNA sequences","volume":"317","author":"Mathews","year":"2002","journal-title":"J. Mol. Biol"},{"key":"2024021913335906200_btaa431-B17","doi-asserted-by":"crossref","first-page":"2075","DOI":"10.1261\/rna.1556009","article-title":"The tedious task of finding homologous noncoding RNA genes","volume":"15","author":"Menzel","year":"2009","journal-title":"RNA"},{"key":"2024021913335906200_btaa431-B18","doi-asserted-by":"crossref","first-page":"2089","DOI":"10.1093\/bioinformatics\/btx114","article-title":"RNAscClust: clustering RNA sequences using structure conservation and graph based motifs","volume":"33","author":"Miladi","year":"2017","journal-title":"Bioinformatics"},{"key":"2024021913335906200_btaa431-B19","doi-asserted-by":"crossref","first-page":"giz150","DOI":"10.1093\/gigascience\/giz150","article-title":"Graphclust2: annotation and discovery of structured RNAs with scalable and accessible integrative clustering","volume":"8","author":"Miladi","year":"2019","journal-title":"GigaScience"},{"key":"2024021913335906200_btaa431-B20","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.4161\/rna.25038","article-title":"Computational identification of functional RNA homologs in metagenomic data","volume":"10","author":"Nawrocki","year":"2013","journal-title":"RNA Biol"},{"key":"2024021913335906200_btaa431-B21","doi-asserted-by":"crossref","first-page":"4307","DOI":"10.1093\/nar\/gkt101","article-title":"CompaRNA: a server for continuous benchmarking of automated methods for RNA secondary structure prediction","volume":"41","author":"Puton","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2024021913335906200_btaa431-B22","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment and protosequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math"},{"key":"2024021913335906200_btaa431-B23","doi-asserted-by":"crossref","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","article-title":"A comprehensive comparison of multiple sequence alignment programs","volume":"27","author":"Thompson","year":"1999","journal-title":"Nucleic Acids Res"},{"key":"2024021913335906200_btaa431-B24","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","article-title":"Multiple structural alignment and clustering of RNA sequences","volume":"23","author":"Torarinsson","year":"2007","journal-title":"Bioinformatics"},{"key":"2024021913335906200_btaa431-B25","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1261\/rna.2536111","article-title":"Rnacode: robust discrimination of coding and noncoding regions in comparative sequence data","volume":"17","author":"Washietl","year":"2011","journal-title":"RNA"},{"key":"2024021913335906200_btaa431-B26","doi-asserted-by":"crossref","first-page":"2487","DOI":"10.1093\/bioinformatics\/btt403","article-title":"nhmmer: DNA homology search with profile hmms","volume":"29","author":"Wheeler","year":"2013","journal-title":"Bioinformatics"},{"key":"2024021913335906200_btaa431-B27","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":"2024021913335906200_btaa431-B28","doi-asserted-by":"crossref","first-page":"2489","DOI":"10.1093\/bioinformatics\/btv185","article-title":"SPARSE: quadratic time simultaneous alignment and folding of RNAs without sequence-based heuristics","volume":"31","author":"Will","year":"2015","journal-title":"Bioinformatics"},{"key":"2024021913335906200_btaa431-B29","doi-asserted-by":"crossref","first-page":"19","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"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i242\/56702217\/bioinformatics_36_supplement1_i242.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/Supplement_1\/i242\/56702217\/bioinformatics_36_supplement1_i242.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T13:43:24Z","timestamp":1708350204000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/Supplement_1\/i242\/5870506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,1]]},"references-count":29,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2020,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa431","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2020,7]]},"published":{"date-parts":[[2020,7,1]]}}}