{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T22:10:42Z","timestamp":1757455842498,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["BA2168\/16-1","BA2168\/21-1","BA2168\/3-3","CIBSS-EXC-2189-Project ID 390939984"],"award-info":[{"award-number":["BA2168\/16-1","BA2168\/21-1","BA2168\/3-3","CIBSS-EXC-2189-Project ID 390939984"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Austrian Science Fund","award":["2874-N28"],"award-info":[{"award-number":["2874-N28"]}]},{"name":"Projekt DEAL"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Motivation<\/jats:title>\n                <jats:p>Simultaneous alignment and folding (SA&amp;F) of RNAs is the indispensable gold standard for inferring the structure of non-coding RNAs and their general analysis. The original algorithm, proposed by Sankoff, solves the theoretical problem exactly with a complexity of <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^6)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mn>6<\/mml:mn>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in the full energy model. Over the last two decades, several variants and improvements of the Sankoff algorithm have been proposed to reduce its extreme complexity by proposing simplified energy models or imposing restrictions on the predicted alignments.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>Here, we introduce a novel variant of Sankoff\u2019s algorithm that reconciles the simplifications of PMcomp, namely moving from the full energy model to a simpler base pair-based model, with the accuracy of the loop-based full energy model. Instead of estimating pseudo-energies from unconditional base pair probabilities, our model calculates energies from conditional base pair probabilities that allow to accurately capture structure probabilities, which obey a conditional dependency. This model gives rise to the fast and highly accurate novel algorithm Pankov (Probabilistic Sankoff-like simultaneous alignment and folding of RNAs inspired by Markov chains).<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>Pankov benefits from the speed-up of excluding unreliable base-pairing without compromising the loop-based free energy model of the Sankoff\u2019s algorithm. We show that Pankov outperforms its predecessors LocARNA and SPARSE in folding quality and is faster than LocARNA.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-020-00179-w","type":"journal-article","created":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T18:02:57Z","timestamp":1605290577000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast and accurate structure probability estimation for simultaneous alignment and folding of RNAs with Markov chains"],"prefix":"10.1186","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0173-3009","authenticated-orcid":false,"given":"Milad","family":"Miladi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Raden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8231-3323","authenticated-orcid":false,"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"issue":"1","key":"179_CR1","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.cell.2014.03.008","volume":"157","author":"TR Cech","year":"2014","unstructured":"Cech TR, Steitz JA. The noncoding RNA revolution-trashing old rules to forge new ones. Cell. 2014;157(1):77\u201394.","journal-title":"Cell"},{"key":"179_CR2","doi-asserted-by":"crossref","unstructured":"Seetin MG, Mathews DH. RNA structure prediction: an overview of methods. In: Bacterial Regulatory RNA, editor. Totowa: Humana Press; 2012. p. 99\u2013122.","DOI":"10.1007\/978-1-61779-949-5_8"},{"issue":"5","key":"179_CR3","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D Sankoff","year":"1985","unstructured":"Sankoff D. Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J Appl Math. 1985;45(5):810\u201325.","journal-title":"SIAM J Appl Math"},{"issue":"8","key":"179_CR4","doi-asserted-by":"publisher","first-page":"2433","DOI":"10.1093\/nar\/gki541","volume":"33","author":"PP Gardner","year":"2005","unstructured":"Gardner PP, Wilm A, Washietl S. A benchmark of multiple sequence alignment programs upon structural RNAs. Nucleic Acids Res. 2005;33(8):2433\u20139.","journal-title":"Nucleic Acids Res"},{"issue":"14","key":"179_CR5","doi-asserted-by":"publisher","first-page":"2089","DOI":"10.1093\/bioinformatics\/btx114","volume":"33","author":"M Miladi","year":"2017","unstructured":"Miladi M, Junge A, Costa F, Seemann SE, Havgaard JH, Gorodkin J, et al. RNAscClust: clustering RNA sequences using structure conservation and graph based motifs. Bioinformatics. 2017;33(14):2089\u201396.","journal-title":"Bioinformatics"},{"issue":"2","key":"179_CR6","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jmbi.2001.5351","volume":"317","author":"DH Mathews","year":"2002","unstructured":"Mathews DH, Turner DH. Dynalign: an algorithm for finding the secondary structure common to two RNA sequences. J Mol Biol. 2002;317(2):191\u2013203.","journal-title":"J Mol Biol"},{"issue":"9","key":"179_CR7","doi-asserted-by":"publisher","first-page":"1815","DOI":"10.1093\/bioinformatics\/bti279","volume":"21","author":"JH Havgaard","year":"2005","unstructured":"Havgaard JH, Lyngs\u00f8 RB, Stormo GD, Gorodkin J. Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. Bioinformatics. 2005;21(9):1815\u201324.","journal-title":"Bioinformatics"},{"issue":"5","key":"179_CR8","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","volume":"288","author":"D Mathews","year":"1999","unstructured":"Mathews D, Sabina J, Zuker M, Turner D. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol. 1999;288(5):911\u201340.","journal-title":"J Mol Biol"},{"issue":"14","key":"179_CR9","doi-asserted-by":"publisher","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","volume":"20","author":"IL Hofacker","year":"2004","unstructured":"Hofacker IL, Bernhart SH, Stadler PF. Alignment of RNA base pairing probability matrices. Bioinformatics. 2004;20(14):2222\u20137.","journal-title":"Bioinformatics"},{"issue":"6\u20137","key":"179_CR10","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"JS McCaskill","year":"1990","unstructured":"McCaskill JS. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers. 1990;29(6\u20137):1105\u201319.","journal-title":"Biopolymers"},{"issue":"4","key":"179_CR11","doi-asserted-by":"publisher","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","volume":"3","author":"S Will","year":"2007","unstructured":"Will S, Reiche K, Hofacker IL, Stadler PF, Backofen R. Inferring non-coding RNA families and classes by means of genome-scale structure-based clustering. PLoS Comput Biol. 2007;3(4):e65.","journal-title":"PLoS Comput Biol"},{"issue":"8","key":"179_CR12","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","volume":"23","author":"E Torarinsson","year":"2007","unstructured":"Torarinsson E, Havgaard JH, Gorodkin J. Multiple structural alignment and clustering of RNA sequences. Bioinformatics. 2007;23(8):926\u201332.","journal-title":"Bioinformatics"},{"key":"179_CR13","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1186\/1471-2105-8-130","volume":"8","author":"AO Harmanci","year":"2007","unstructured":"Harmanci AO, Sharma G, Mathews DH. Efficient pairwise RNA structure prediction using probabilistic alignment constraints in Dynalign. BMC Bioinformatics. 2007;8:130.","journal-title":"BMC Bioinformatics"},{"issue":"13","key":"179_CR14","doi-asserted-by":"publisher","first-page":"1588","DOI":"10.1093\/bioinformatics\/btm146","volume":"23","author":"H Kiryu","year":"2007","unstructured":"Kiryu H, Tabei Y, Kin T, Asai K. Murlet: a practical multiple alignment tool for structural RNA sequences. Bioinformatics. 2007;23(13):1588\u201398.","journal-title":"Bioinformatics"},{"issue":"15","key":"179_CR15","doi-asserted-by":"publisher","first-page":"2489","DOI":"10.1093\/bioinformatics\/btv185","volume":"31","author":"S Will","year":"2015","unstructured":"Will S, Otto C, Miladi M, M\u00f6hl M, Backofen R. SPARSE: quadratic time simultaneous alignment and folding of RNAs without sequence-based heuristics. Bioinformatics. 2015;31(15):2489\u201396.","journal-title":"Bioinformatics"},{"issue":"1","key":"179_CR16","doi-asserted-by":"publisher","first-page":"6602","DOI":"10.1186\/s12859-014-0404-0","volume":"15","author":"C Otto","year":"2014","unstructured":"Otto C, Mohl M, Heyne S, Amit M, Landau GM, Backofen R, et al. ExpaRNA-P: simultaneous exact pattern matching and folding of RNAs. BMC Bioinformatics. 2014;15(1):6602.","journal-title":"BMC Bioinformatics"},{"issue":"11","key":"179_CR17","doi-asserted-by":"publisher","first-page":"5381","DOI":"10.1093\/nar\/gky285","volume":"46","author":"P Danaee","year":"2018","unstructured":"Danaee P, Rouches M, Wiley M, Deng D, Huang L, Hendrix D. bpRNA: large-scale automated annotation and analysis of RNA secondary structure. Nucleic Acids Res. 2018;46(11):5381\u201394.","journal-title":"Nucleic Acids Res"},{"issue":"1\u20132","key":"179_CR18","first-page":"129","volume":"56","author":"AF Bompf\u00fcnewerer","year":"2008","unstructured":"Bompf\u00fcnewerer AF, Backofen R, Bernhart SH, Hertel J, Hofacker IL, Stadler PF, et al. Variations on RNA folding and alignment: lessons from Benasque. J Math Biol. 2008;56(1\u20132):129\u201344.","journal-title":"J Math Biol"},{"issue":"22","key":"179_CR19","doi-asserted-by":"publisher","first-page":"13939","DOI":"10.1093\/nar\/gku1172","volume":"42","author":"Y Fu","year":"2014","unstructured":"Fu Y, Sharma G, Mathews DH. Dynalign II: common secondary structure prediction for RNA homologs with domain insertions. Nucleic Acids Res. 2014;42(22):13939\u201348.","journal-title":"Nucleic Acids Res"},{"issue":"2","key":"179_CR20","first-page":"145","volume":"49","author":"S Wuchty","year":"1999","unstructured":"Wuchty S, Fontana W, Hofacker IL, Schuster P. Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers Original Res Biomol. 1999;49(2):145\u201365.","journal-title":"Biopolymers Original Res Biomol"},{"key":"179_CR21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1186\/1748-7188-1-19","volume":"1","author":"A Wilm","year":"2006","unstructured":"Wilm A, Mainz I, Steger G. An enhanced RNA alignment benchmark for sequence alignment programs. Algorithms Mol Biol. 2006;1:19.","journal-title":"Algorithms Mol Biol"},{"issue":"10","key":"179_CR22","doi-asserted-by":"publisher","first-page":"2135","DOI":"10.1093\/nar\/29.10.2135","volume":"29","author":"J Gorodkin","year":"2001","unstructured":"Gorodkin J, Stricklin SL, Stormo GD. Discovering common stem-loop motifs in unaligned RNA sequences. Nucleic Acids Res. 2001;29(10):2135\u201344.","journal-title":"Nucleic Acids Res"},{"issue":"2","key":"179_CR23","first-page":"306","volume":"18","author":"B L\u00f6wes","year":"2016","unstructured":"L\u00f6wes B, Chauve C, Ponty Y, Giegerich R. The BRaliBase dent-a tale of benchmark design and interpretation. Brief Bioinformatics. 2016;18(2):306\u201311.","journal-title":"Brief Bioinformatics"},{"issue":"1","key":"179_CR24","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1186\/1471-2105-5-71","volume":"5","author":"RD Dowell","year":"2004","unstructured":"Dowell RD, Eddy SR. Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics. 2004;5(1):71.","journal-title":"BMC Bioinformatics"},{"key":"179_CR25","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1186\/1471-2105-7-400","volume":"7","author":"RD Dowell","year":"2006","unstructured":"Dowell RD, Eddy SR. Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints. BMC Bioinformatics. 2006;7:400.","journal-title":"BMC Bioinformatics"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00179-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-020-00179-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00179-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,14]],"date-time":"2020-11-14T06:03:16Z","timestamp":1605333796000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-020-00179-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["179"],"URL":"https:\/\/doi.org\/10.1186\/s13015-020-00179-w","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"18 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"19"}}