{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:01:03Z","timestamp":1767859263178,"version":"3.49.0"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,8]]},"abstract":"<jats:p> Pairwise ordered tree alignment are combinatorial objects that appear in important applications, such as RNA secondary structure comparison. However, the usual representation of tree alignments as supertrees is ambiguous, i.e. two distinct supertrees may induce identical sets of matches between identical pairs of trees. This ambiguity is uninformative, and detrimental to any probabilistic analysis. <\/jats:p><jats:p> In this work, we consider tree alignments up to equivalence. Our first result is a precise asymptotic enumeration of tree alignments, obtained from a context-free grammar by mean of basic analytic combinatorics. Our second result focuses on alignments between two given ordered trees [Formula: see text] and [Formula: see text]. By refining our grammar to align specific trees, we obtain a decomposition scheme for the space of alignments, and use it to design an efficient dynamic programming algorithm for sampling alignments under the Gibbs-Boltzmann probability distribution. This generalizes existing tree alignment algorithms, and opens the door for a probabilistic analysis of the space of suboptimal alignments. <\/jats:p>","DOI":"10.1142\/s0129054118420030","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T10:47:08Z","timestamp":1534848428000},"page":"741-767","source":"Crossref","is-referenced-by-count":2,"title":["Counting, Generating, Analyzing and Sampling Tree Alignments"],"prefix":"10.1142","volume":"29","author":[{"given":"Cedric","family":"Chauve","sequence":"first","affiliation":[{"name":"Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, B.C. V5A 1S6, Canada"}]},{"given":"Julien","family":"Courtiel","sequence":"additional","affiliation":[{"name":"Laboratoire d\u2019Informatique de Paris Nord, Universit\u00e9 Paris 13, 99, Avenue Jean-Baptiste Cl\u00e9ment 93430 Villetaneuse, France"}]},{"given":"Yann","family":"Ponty","sequence":"additional","affiliation":[{"name":"LIX CNRS UMR 7161, Ecole Polytechnique, Universit\u00e9 Paris-Saclay, AMIBio Team, Inria Saclay, Universit\u00e9 Paris-Saclay, Bat. Alan Turing, 1 rue d\u2019Estienne d\u2019Orves Palaiseau, 91120, France"}]}],"member":"219","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"S0129054118420030BIB002","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-94"},{"key":"S0129054118420030BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2008.28"},{"key":"S0129054118420030BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.010"},{"key":"S0129054118420030BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/11732990_15"},{"key":"S0129054118420030BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-9659(98)00054-8"},{"key":"S0129054118420030BIB008","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<103::AID-RSA5>3.0.CO;2-Z"},{"key":"S0129054118420030BIB012","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0129054118420030BIB013","doi-asserted-by":"publisher","DOI":"10.3390\/a7010062"},{"key":"S0129054118420030BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.014"},{"key":"S0129054118420030BIB015","first-page":"159","volume":"2","author":"H\u00f6chsmann M.","year":"2003","journal-title":"Proc IEEE Comput Soc Bioinform Conf."},{"key":"S0129054118420030BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2004.11"},{"key":"S0129054118420030BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)80029-9"},{"key":"S0129054118420030BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"S0129054118420030BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.07.040"},{"key":"S0129054118420030BIB022","doi-asserted-by":"publisher","DOI":"10.1080\/10425170310001617894"},{"key":"S0129054118420030BIB023","doi-asserted-by":"publisher","DOI":"10.1093\/protein\/3.7.565"},{"key":"S0129054118420030BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-6846-3"},{"key":"S0129054118420030BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/S0001-8708(77)80046-7"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118420030","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:58:08Z","timestamp":1565182688000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118420030"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":18,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2018,8,21]]},"published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.1142\/S0129054118420030"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118420030","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}