{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:45:31Z","timestamp":1740185131461,"version":"3.37.3"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2019,1,10]],"date-time":"2019-01-10T00:00:00Z","timestamp":1547078400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1149544","CCF-1447235"],"award-info":[{"award-number":["CCF-1149544","CCF-1447235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"United States Department of Agriculture National Institute of Food and Agriculture","award":["USDA-NIFASCRI-2017-51181-26834"],"award-info":[{"award-number":["USDA-NIFASCRI-2017-51181-26834"]}]},{"name":"National Center of Excellence for Melon"},{"name":"Vegetable and Fruit Improvement Center of Texas A&M University"},{"name":"TEES-AgriLife Center for Bioinformatics and Genomic Systems Engineering"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>For many RNA families, the secondary structure is known to be better conserved among the member RNAs compared to the primary sequence. For this reason, it is important to consider the underlying folding structures when aligning RNA sequences, especially for those with relatively low sequence identity. Given a set of RNAs with unknown structures, simultaneous RNA alignment and folding algorithms aim to accurately align the RNAs by jointly predicting their consensus secondary structure and the optimal sequence alignment. Despite the improved accuracy of the resulting alignment, the computational complexity of simultaneous alignment and folding for a pair of RNAs is O(N6), which is too costly to be used for large-scale analysis.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In order to address this shortcoming, in this work, we propose a novel network-based scheme for pairwise structural alignment of RNAs. The proposed algorithm, TOPAS, builds on the concept of topological networks that provide structural maps of the RNAs to be aligned. For each RNA sequence, TOPAS first constructs a topological network based on the predicted folding structure, which consists of sequential edges and structural edges weighted by the base-pairing probabilities. The obtained networks can then be efficiently aligned by using probabilistic network alignment techniques, thereby yielding the structural alignment of the RNAs. The computational complexity of our proposed method is significantly lower than that of the Sankoff-style dynamic programming approach, while yielding favorable alignment results. Furthermore, another important advantage of the proposed algorithm is its capability of handling RNAs with pseudoknots while predicting the RNA structural alignment. We demonstrate that TOPAS generally outperforms previous RNA structural alignment methods on RNA benchmarks in terms of both speed and accuracy.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Source code of TOPAS and the benchmark data used in this paper are available at https:\/\/github.com\/bjyoontamu\/TOPAS.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btz001","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T20:11:19Z","timestamp":1546632679000},"page":"2941-2948","source":"Crossref","is-referenced-by-count":8,"title":["TOPAS: network-based structural alignment of RNA sequences"],"prefix":"10.1093","volume":"35","author":[{"given":"Chun-Chi","family":"Chen","sequence":"first","affiliation":[{"name":"Texas A&M University, College Station Department of Electrical and Computer Engineering, , TX, USA"},{"name":"TEES-AgriLife Center for Bioinformatics & Genomic Systems Engineering, Texas A&M University, College Station , TX, USA"}]},{"given":"Hyundoo","family":"Jeong","sequence":"additional","affiliation":[{"name":"Chosun University Department of Electronic Engineering, , Gwangju, Republic of Korea"}]},{"given":"Xiaoning","family":"Qian","sequence":"additional","affiliation":[{"name":"Texas A&M University, College Station Department of Electrical and Computer Engineering, , TX, USA"},{"name":"TEES-AgriLife Center for Bioinformatics & Genomic Systems Engineering, Texas A&M University, College Station , TX, USA"}]},{"given":"Byung-Jun","family":"Yoon","sequence":"additional","affiliation":[{"name":"Texas A&M University, College Station Department of Electrical and Computer Engineering, , TX, USA"},{"name":"TEES-AgriLife Center for Bioinformatics & Genomic Systems Engineering, Texas A&M University, College Station , TX, USA"}]}],"member":"286","published-online":{"date-parts":[[2019,1,10]]},"reference":[{"key":"2023062803480245200_btz001-B2","doi-asserted-by":"crossref","first-page":"i68","DOI":"10.1093\/bioinformatics\/btn177","article-title":"A max-margin model for efficient simultaneous alignment and folding of RNA sequences","volume":"24","author":"Chuong","year":"2008","journal-title":"Bioinformatics"},{"key":"2023062803480245200_btz001-B1","doi-asserted-by":"crossref","first-page":"1974","DOI":"10.1093\/bioinformatics\/btp250","article-title":"VARNA: interactive drawing and editing of the RNA secondary structure","volume":"25","author":"Darty","year":"2009","journal-title":"Bioinformatics"},{"key":"2023062803480245200_btz001-B3","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1017\/S1355838200992161","article-title":"RNA folding at elementary step resolution","volume":"6","author":"Flamm","year":"2000","journal-title":"RNA"},{"key":"2023062803480245200_btz001-B4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1101\/gr.5890907","article-title":"Exploring genomic dark matter: a critical assessment of the performance of homology search methods on noncoding RNA","volume":"17","author":"Freyhult","year":"2006","journal-title":"Genome Res"},{"key":"2023062803480245200_btz001-B5","doi-asserted-by":"crossref","first-page":"13939","DOI":"10.1093\/nar\/gku1172","article-title":"Dynalign II: common secondary structure prediction for RNA homologs with domain insertions","volume":"42","author":"Fu","year":"2014","journal-title":"Nucleic Acids Res"},{"key":"2023062803480245200_btz001-B6","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":"2023062803480245200_btz001-B7","doi-asserted-by":"crossref","first-page":"3287","DOI":"10.1093\/nar\/9.14.3287","article-title":"Secondary structure of the large subunit ribosomal RNA from Escherichia coli, Zea mays chloroplast, and human and mouse mitochondrial ribosomes","volume":"9","author":"Glotz","year":"1981","journal-title":"Nucleic Acids Res"},{"key":"2023062803480245200_btz001-B8","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1126\/science.1151298","article-title":"Direct observation of hierarchical folding in single riboswitch aptamers","volume":"319","author":"Greenleaf","year":"2008","journal-title":"Science"},{"key":"2023062803480245200_btz001-B9","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1093\/nar\/gkg006","article-title":"Rfam: an RNA family database","volume":"31","author":"Griffiths-Jones","year":"2003","journal-title":"Nucleic Acids Res"},{"key":"2023062803480245200_btz001-B10","doi-asserted-by":"crossref","first-page":"1398","DOI":"10.1042\/BST0361398","article-title":"Topological properties of protein interaction networks from a structural perspective","volume":"36","author":"Gursoy","year":"2008","journal-title":"Biochem. Soc. Trans"},{"key":"2023062803480245200_btz001-B11","doi-asserted-by":"crossref","first-page":"3236","DOI":"10.1093\/bioinformatics\/btp580","article-title":"CentroidAlign: fast and accurate aligner for structured RNAs by maximizing expected sum-of-pairs score","volume":"25","author":"Hamada","year":"2009","journal-title":"Bioinformatics"},{"key":"2023062803480245200_btz001-B12","doi-asserted-by":"crossref","first-page":"2406","DOI":"10.1093\/nar\/gkn043","article-title":"PARTS: probabilistic alignment for RNA joinT secondary structure prediction","volume":"36","author":"Harmanci","year":"2008","journal-title":"Nucleic Acids Res"},{"key":"2023062803480245200_btz001-B13","doi-asserted-by":"crossref","first-page":"1815","DOI":"10.1093\/bioinformatics\/bti279","article-title":"Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%","volume":"21","author":"Havgaard","year":"2005","journal-title":"Bioinformatics"},{"key":"2023062803480245200_btz001-B14","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1002\/0471250953.bi1202s26","article-title":"RNA secondary structure analysis using the Vienna RNA package","volume":"26","author":"Hofacker","year":"2009","journal-title":"Curr. Protoc. Bioinformatics"},{"key":"2023062803480245200_btz001-B15","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":"2023062803480245200_btz001-B16","doi-asserted-by":"crossref","first-page":"S7","DOI":"10.1186\/1752-0509-9-S1-S7","article-title":"Accurate multiple network alignment through context-sensitive random walk","volume":"9","author":"Jeong","year":"2015","journal-title":"BMC Syst. Biol"},{"key":"2023062803480245200_btz001-B17","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1186\/s12859-016-1215-2","article-title":"Effective comparative analysis of protein\u2013protein interaction networks by measuring the steady-state network flow using a Markov model","volume":"17","author":"Jeong","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023062803480245200_btz001-B18","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1016\/j.bbagen.2013.10.035","article-title":"Evolutionary conservation of long non-coding RNAs; sequence, structure, function","volume":"1840","author":"Johnsson","year":"2014","journal-title":"Biochim. Biophys. Acta"},{"key":"2023062803480245200_btz001-B19","doi-asserted-by":"crossref","first-page":"i253","DOI":"10.1093\/bioinformatics\/btp203","article-title":"IsoRankN: spectral methods for global alignment of multiple protein networks","volume":"25","author":"Liao","year":"2009","journal-title":"Bioinformatics"},{"key":"2023062803480245200_btz001-B20","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1261\/rna.7650904","article-title":"Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization","volume":"10","author":"Mathews","year":"2004","journal-title":"RNA"},{"key":"2023062803480245200_btz001-B21","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":"2023062803480245200_btz001-B22","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1002\/bip.360290621","article-title":"The equilibrium partition function and base pair binding probabilities for RNA secondary structure","volume":"29","author":"McCaskill","year":"1990","journal-title":"Biopolymers"},{"key":"2023062803480245200_btz001-B23","doi-asserted-by":"crossref","first-page":"pdb","DOI":"10.1101\/pdb.top41","article-title":"Using hidden Markov models to align multiple sequences","volume":"2009","author":"Mount","year":"2009","journal-title":"Cold Spring Harb. Protoc"},{"key":"2023062803480245200_btz001-B24","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0079-6107(88)90011-9","article-title":"Evolutionary conservation of structure and function of high molecular weight ribosomal RNA","volume":"51","author":"Rau\u00e9","year":"1988","journal-title":"Progress Biophys. Mol. Biol"},{"key":"2023062803480245200_btz001-B25","doi-asserted-by":"crossref","first-page":"1.","DOI":"10.1186\/1471-2105-11-129","article-title":"RNAstructure: software for RNA secondary structure prediction and analysis","volume":"11","author":"Reuter","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023062803480245200_btz001-B26","doi-asserted-by":"crossref","first-page":"e67995.","DOI":"10.1371\/journal.pone.0067995","article-title":"SMETANA: accurate and scalable algorithm for probabilistic alignment of large-scale biological networks","volume":"8","author":"Sahraeian","year":"2013","journal-title":"PloS One"},{"key":"2023062803480245200_btz001-B27","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":"2023062803480245200_btz001-B28","doi-asserted-by":"crossref","first-page":"12763","DOI":"10.1073\/pnas.0806627105","article-title":"Global alignment of multiple protein interaction networks with application to functional orthology detection","volume":"105","author":"Singh","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023062803480245200_btz001-B29","doi-asserted-by":"crossref","first-page":"1238","DOI":"10.1093\/bioinformatics\/btv748","article-title":"Foldalign 2.5: multithreaded implementation for pairwise structural RNA alignment","volume":"32","author":"Sundfeld","year":"2016","journal-title":"Bioinformatics"},{"key":"2023062803480245200_btz001-B30","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":"2023062803480245200_btz001-B31","doi-asserted-by":"crossref","first-page":"D280","DOI":"10.1093\/nar\/gkp892","article-title":"NNDB: the nearest neighbor parameter database for predicting stability of nucleic acid secondary structure","volume":"38","author":"Turner","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2023062803480245200_btz001-B32","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":"2023062803480245200_btz001-B33","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":"2023062803480245200_btz001-B34","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":"2023062803480245200_btz001-B35","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":"2023062803480245200_btz001-B36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2164-15-S1-S14","article-title":"Sequence alignment by passing messages","volume":"15","author":"Yoon","year":"2014","journal-title":"BMC Genomics"},{"key":"2023062803480245200_btz001-B37","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1109\/MSP.2011.942819","article-title":"Comparative analysis of biological networks: hidden Markov model and Markov chain-based approach","volume":"29","author":"Yoon","year":"2012","journal-title":"IEEE Signal Process. Mag"},{"key":"2023062803480245200_btz001-B38","doi-asserted-by":"crossref","first-page":"3621","DOI":"10.1093\/nar\/9.15.3621","article-title":"Secondary structure comparisons between small subunit ribosomal RNA molecules from six different species","volume":"9","author":"Zwieb","year":"1981","journal-title":"Nucleic Acids Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/17\/2941\/50719958\/bioinformatics_35_17_2941.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/17\/2941\/50719958\/bioinformatics_35_17_2941.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T03:48:47Z","timestamp":1687924127000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/17\/2941\/5284906"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,1,10]]},"references-count":38,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2019,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz001","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2019,9,1]]},"published":{"date-parts":[[2019,1,10]]}}}