{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T12:38:59Z","timestamp":1777120739192,"version":"3.51.4"},"reference-count":37,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T00:00:00Z","timestamp":1773100800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN-2016-06051"],"award-info":[{"award-number":["RGPIN-2016-06051"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003151","name":"Fonds de recherche du Qu\u00e9bec \u2013 Nature et technologies","doi-asserted-by":"crossref","award":["86843-23"],"award-info":[{"award-number":["86843-23"]}],"id":[{"id":"10.13039\/501100003151","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Biology"],"published-print":{"date-parts":[[2026,4,1]]},"abstract":"<jats:p>\n                    The reconstruction of ancestral non-coding RNA (ncRNA) sequences is particularly challenging due to the main conservation forces being applied to the structure, rather than the sequence. Naively trying to preserve the structure during the reconstruction tends to produce ancestors that are more energetically fit to the structure than their descendants, a clear contradiction. While most sequences are associated to only one functional structure, RNA families have an old and complex history. It has been hypothesized that some ancestral RNAs were combining multiple functions, with multistable structures. At some point, a duplication event happened, and each copy subspecialized into a specific structure. To circumvent the bias introduced by reconstructing sequences when only one structure is conserved, we recently proposed an approach using substitution and base pair costs that focuses on simultaneously reconstructing the ancestor of two related ncRNA families, assuming that they were created by this process of duplication followed by subspecialization. In this work, we improve the previous approach by leveraging advances in tree decomposition algorithms to (1) incorporate simultaneously more constraints and positions in the reconstruction which (2) allows to use a more realistic energetic model. Results on simulated datasets demonstrate significant improvements in ancestral sequence inference accuracy while reducing the number of optimal sequences inferred by several orders of magnitude. On real datasets of RFam clans (\n                    <jats:italic toggle=\"yes\">Glm<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">FinP-traJ<\/jats:italic>\n                    ), we show that the new approach is able to infer fewer optimal ancestral sequences that are more fit to both structures compared with previous methods.\n                  <\/jats:p>","DOI":"10.1177\/15578666261423964","type":"journal-article","created":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T13:12:38Z","timestamp":1773234758000},"page":"499-517","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Reconstructing Ancestral Non-Coding RNAs of Multiple Families Using Sequence and Structural Information with Tree Decomposition"],"prefix":"10.1177","volume":"33","author":[{"given":"Songdi","family":"Hu","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada."}]},{"given":"Vladimir","family":"Reinharz","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019informatique, Universit\u00e9 du Qu\u00e9bec \u00e0 Montr\u00e9al, Montr\u00e9al, Qu\u00e9bec, Canada."}]},{"given":"Olivier","family":"Tremblay-Savard","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada."}]}],"member":"179","published-online":{"date-parts":[[2026,3,10]]},"reference":[{"issue":"1","key":"e_1_3_3_2_1","first-page":"26","article-title":"Genome-scale evolution: Reconstructing gene orders in the ancestral species","volume":"12","author":"Bourque G","year":"2002","unstructured":"Bourque G, , Pevzner PA. Genome-scale evolution: Reconstructing gene orders in the ancestral species. Genome Res, 2002; 12(1):26\u201336.","journal-title":"Genome Res"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000483"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-51"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/22.11.2079"},{"key":"e_1_3_3_7_1","unstructured":"EMBL-EBI. Glossary: Clan. 2026. Available from: https:\/\/docs.rfam.org\/en\/latest\/glossary.html"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/20.4.406"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00706-008-0895-3"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1355838200992161"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1355838201000863"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27801-6_17"},{"key":"e_1_3_3_13_1","unstructured":"Hagberg A Conway D. NetworkX: Network analysis with Python. 2020. Available from: https:\/\/networkx.org\/"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-019-2784-7"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1002752"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1998.2404"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/15.6.446"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199299188.001.0001"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-6-26"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-260"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btae229"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-022-00213-z"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.07.027"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkac1003"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33122-0_12"},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1998.5.555"},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045092"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0128004"},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-022-00216-w"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gks491"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00011-9"},{"issue":"1","key":"e_1_3_3_32_1","article-title":"Reconstruction of ancestral RNA sequences under multiple structural constraints","volume":"17","author":"Tremblay-Savard O","year":"2016","unstructured":"Tremblay-Savard O, , Reinharz V, , Waldisp\u00fchl J. Reconstruction of ancestral RNA sequences under multiple structural constraints. BMC Genomics, 2016; 17(Suppl 1):862\u2013186.","journal-title":"BMC Genomics"},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pbio.0060064"},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msm088"},{"key":"e_1_3_3_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btk008"},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2164-14-S7-S3"},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn146"},{"key":"e_1_3_3_38_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/9.1.133"}],"container-title":["Journal of Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261423964","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/15578666261423964","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261423964","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T11:49:25Z","timestamp":1777117765000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/15578666261423964"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,10]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,4,1]]}},"alternative-id":["10.1177\/15578666261423964"],"URL":"https:\/\/doi.org\/10.1177\/15578666261423964","relation":{},"ISSN":["1066-5277","1557-8666"],"issn-type":[{"value":"1066-5277","type":"print"},{"value":"1557-8666","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,10]]}}}