{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:40:43Z","timestamp":1757626843998,"version":"3.44.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031949272"},{"type":"electronic","value":"9783031949289"}],"license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-031-94928-9_3","type":"book-chapter","created":{"date-parts":[[2025,8,31]],"date-time":"2025-08-31T09:46:55Z","timestamp":1756633615000},"page":"27-50","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tree Decomposition for\u00a0Reconstructing Ancestral RNA Sequences of\u00a0Multiple Families"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8541-1356","authenticated-orcid":false,"given":"Songdi","family":"Hu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8481-1094","authenticated-orcid":false,"given":"Vladimir","family":"Reinharz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2514-0264","authenticated-orcid":false,"given":"Olivier","family":"Tremblay-Savard","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,1]]},"reference":[{"issue":"1","key":"3_CR1","first-page":"26","volume":"12","author":"G Bourque","year":"2002","unstructured":"Bourque, G., Pevzner, P.A.: Genome-scale evolution: reconstructing gene orders in the ancestral species. Genome Res. 12(1), 26\u201336 (2002)","journal-title":"Genome Res."},{"issue":"8","key":"3_CR2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000483","volume":"5","author":"RK Bradley","year":"2009","unstructured":"Bradley, R.K., Holmes, I.: Evolutionary Triplet Models of Structured RNA. PLoS Comput. Biol. 5(8), e1000483 (2009)","journal-title":"PLoS Comput. Biol."},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1186\/1471-2105-10-51","volume":"10","author":"JC Clemente","year":"2009","unstructured":"Clemente, J.C., Ikeo, K., Valiente, G., Gojobori, T.: Optimized ancestral state reconstruction using Sankoff parsimony. BMC Bioinform. 10(1), 51 (2009)","journal-title":"BMC Bioinform."},{"issue":"11","key":"3_CR4","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","volume":"22","author":"SR Eddy","year":"1994","unstructured":"Eddy, S.R., Durbin, R.: RNA sequence analysis using covariance models. Nucleic Acids Res. 22(11), 2079\u20132088 (1994)","journal-title":"Nucleic Acids Res."},{"key":"3_CR5","unstructured":"EMBL-EBI: Glossary: Clan. https:\/\/docs.rfam.org\/en\/latest\/glossary.html"},{"issue":"4","key":"3_CR6","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","volume":"20","author":"WM Fitch","year":"1971","unstructured":"Fitch, W.M.: Toward defining the course of evolution: minimum change for a specific tree topology. Systematic Biol. 20(4), 406\u2013416 (1971)","journal-title":"Systematic Biol."},{"issue":"2","key":"3_CR7","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1017\/S1355838201000863","volume":"7","author":"C Flamm","year":"2001","unstructured":"Flamm, C., Hofacker, I.L., Maurer-Stroh, S., Stadler, P.F., Zehl, M.: Design of multistable RNA molecules. RNA 7(2), 254\u2013265 (2001)","journal-title":"RNA"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-540-27801-6_17","volume-title":"Combinatorial Pattern Matching","author":"A Gupta","year":"2004","unstructured":"Gupta, A., Ma\u0148uch, J., Stacho, L., Zhu, C.: Small phylogeny problem: character evolution trees. In: Sahinalp, S.C., Muthukrishnan, S., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 230\u2013243. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27801-6_17"},{"key":"3_CR9","unstructured":"Hagberg, A., Conway, D.: NetworkX: Network analysis with Python (2020). https:\/\/networkx.org\/"},{"issue":"1","key":"3_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-019-2784-7","volume":"20","author":"S Hammer","year":"2019","unstructured":"Hammer, S., Wang, W., Will, S., Ponty, Y.: Fixed-parameter tractable sampling for RNA design with multiple target structures. BMC Bioinform. 20(1), 1\u201313 (2019)","journal-title":"BMC Bioinform."},{"issue":"11","key":"3_CR11","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1002752","volume":"8","author":"MP Hoeppner","year":"2012","unstructured":"Hoeppner, M.P., Gardner, P.P., Poole, A.M.: Comparative analysis of RNA families reveals distinct repertoires for each domain of life. PLoS Comput. Biol. 8(11), e1002752 (2012)","journal-title":"PLoS Comput. Biol."},{"issue":"4","key":"3_CR12","doi-asserted-by":"publisher","first-page":"1457","DOI":"10.1006\/jmbi.1998.2404","volume":"285","author":"LJ Jerome","year":"1999","unstructured":"Jerome, L.J., van Biesen, T., Frost, L.S.: Degradation of FinP antisense RNA from F-like plasmids: the RNA-binding protein, FinO, protects FinP from ribonuclease E. J. Mol. Biol. 285(4), 1457\u20131473 (1999)","journal-title":"J. Mol. Biol."},{"issue":"6","key":"3_CR13","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1093\/bioinformatics\/15.6.446","volume":"15","author":"B Knudsen","year":"1999","unstructured":"Knudsen, B., Hein, J.: RNA secondary structure prediction using stochastic context-free grammars and evolutionary history. Bioinformatics 15(6), 446\u2013454 (1999)","journal-title":"Bioinformatics"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Liberles, D.A.: Ancestral Sequence Reconstruction. Oxford University Press on Demand (2007)","DOI":"10.1093\/acprof:oso\/9780199299188.001.0001"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1748-7188-6-26","volume":"6","author":"R Lorenz","year":"2011","unstructured":"Lorenz, R., et al.: ViennaRNA package 2.0. Algorithms Mol. Biol. 6, 1\u201314 (2011)","journal-title":"Algorithms Mol. Biol."},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-13-260","volume":"13","author":"RB Lyngs\u00f8","year":"2012","unstructured":"Lyngs\u00f8, R.B., Anderson, J.W., Sizikova, E., Badugu, A., Hyland, T., Hein, J.: Frnakenstein: multiple target inverse RNA folding. BMC Bioinform. 13, 1\u201312 (2012)","journal-title":"BMC Bioinform."},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Marchand, B., Anselmetti, Y., Lafond, M., Ouangraoua, A.: Median and small parsimony problems on RNA trees. Bioinformatics 40(Supplement_1), i237\u2013i246 (2024)","DOI":"10.1093\/bioinformatics\/btae229"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Marchand, B., Ponty, Y., Bulteau, L.: Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics. Algorithms Mol. Biol. 17(1), 1\u201317 (2022). article no. 8","DOI":"10.1186\/s13015-022-00213-z"},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.tcs.2014.07.027","volume":"552","author":"I Mikl\u00f3s","year":"2014","unstructured":"Mikl\u00f3s, I., Kiss, S.Z., Tannier, E.: Counting and sampling SCJ small parsimony solutions. Theoret. Comput. Sci. 552, 83\u201398 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"D1","key":"3_CR20","doi-asserted-by":"publisher","first-page":"D678","DOI":"10.1093\/nar\/gkac1003","volume":"51","author":"RD Olson","year":"2023","unstructured":"Olson, R.D., et al.: Introducing the bacterial and viral bioinformatics resource center (BV-BRC): a resource combining PATRIC, IRD and ViPR. Nucleic Acids Res. 51(D1), D678\u2013D689 (2023)","journal-title":"Nucleic Acids Res."},{"issue":"1","key":"3_CR21","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D Sankoff","year":"1975","unstructured":"Sankoff, D.: Minimal mutation trees of sequences. SIAM J. Appl. Math. 28(1), 35\u201342 (1975)","journal-title":"SIAM J. Appl. Math."},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BFb0045092","volume-title":"Computing and Combinatorics","author":"D Sankoff","year":"1997","unstructured":"Sankoff, D., Blanchette, M.: The median problem for breakpoints in comparative genomics. In: Jiang, T., Lee, D.T. (eds.) COCOON 1997. LNCS, vol. 1276, pp. 251\u2013263. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/BFb0045092"},{"issue":"3","key":"3_CR23","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1089\/cmb.1998.5.555","volume":"5","author":"D Sankoff","year":"1998","unstructured":"Sankoff, D., Blanchette, M.: Multiple genome rearrangement and breakpoint phylogeny. J. Comput. Biol. 5(3), 555\u2013570 (1998)","journal-title":"J. Comput. Biol."},{"issue":"W1","key":"3_CR24","doi-asserted-by":"publisher","first-page":"W49","DOI":"10.1093\/nar\/gks491","volume":"40","author":"DA Sorescu","year":"2012","unstructured":"Sorescu, D.A., M\u00f6hl, M., Mann, M., Backofen, R., Will, S.: CARNA\u2013alignment of RNA structure ensembles. Nucleic Acids Res. 40(W1), W49\u2013W53 (2012)","journal-title":"Nucleic Acids Res."},{"issue":"3","key":"3_CR25","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/S0022-0000(02)00011-9","volume":"65","author":"G Tesler","year":"2002","unstructured":"Tesler, G.: Efficient algorithms for multichromosomal genome rearrangements. J. Comput. Syst. Sci. 65(3), 587\u2013609 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1186\/s12864-016-3105-4","volume":"17","author":"O Tremblay-Savard","year":"2016","unstructured":"Tremblay-Savard, O., Reinharz, V., Waldisp\u00fchl, J.: Reconstruction of ancestral RNA sequences under multiple structural constraints. BMC Genomics 17, 175\u2013186 (2016)","journal-title":"BMC Genomics"},{"issue":"3","key":"3_CR27","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pbio.0060064","volume":"6","author":"JH Urban","year":"2008","unstructured":"Urban, J.H., Vogel, J.: Two seemingly homologous noncoding RNAs act hierarchically to activate glmS mRNA translation. PLoS Biol. 6(3), e64 (2008)","journal-title":"PLoS Biol."},{"issue":"8","key":"3_CR28","doi-asserted-by":"publisher","first-page":"1586","DOI":"10.1093\/molbev\/msm088","volume":"24","author":"Z Yang","year":"2007","unstructured":"Yang, Z.: PAML 4: phylogenetic analysis by maximum likelihood. Mol. Biol. Evol. 24(8), 1586\u20131591 (2007)","journal-title":"Mol. Biol. Evol."},{"issue":"4","key":"3_CR29","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1093\/bioinformatics\/btk008","volume":"22","author":"Z Yao","year":"2006","unstructured":"Yao, Z., Weinberg, Z., Ruzzo, W.L.: CMfinder\u2013a covariance model based RNA motif finding algorithm. Bioinformatics 22(4), 445\u2013452 (2006)","journal-title":"Bioinformatics"},{"key":"3_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2164-14-S7-S3","volume":"14","author":"C Zheng","year":"2013","unstructured":"Zheng, C., Chen, E., Albert, V.A., Lyons, E., Sankoff, D.: Ancient eudicot hexaploidy meets ancestral Eurosid gene order. BMC Genomics 14, 1\u201313 (2013)","journal-title":"BMC Genomics"},{"issue":"13","key":"3_CR31","doi-asserted-by":"publisher","first-page":"i96","DOI":"10.1093\/bioinformatics\/btn146","volume":"24","author":"C Zheng","year":"2008","unstructured":"Zheng, C., Zhu, Q., Adam, Z., Sankoff, D.: Guided genome halving: hardness, heuristics and the history of the Hemiascomycetes. Bioinformatics 24(13), i96\u2013i104 (2008)","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Comparative Genomics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-94928-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T23:40:39Z","timestamp":1757461239000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-94928-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,1]]},"ISBN":["9783031949272","9783031949289"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-94928-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,9,1]]},"assertion":[{"value":"1 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Authors have no competing interests to declare.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"RECOMB-CG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"RECOMB International Workshop on Comparative Genomics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 April 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 April 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rcg2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb-cg-2025.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}