{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:28:27Z","timestamp":1773275307342,"version":"3.50.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>Phylogeny is both a fundamental tool in biology and a rich source of fascinating modeling and algorithmic problems. Today's wealth of sequenced genomes makes it increasingly important to understand evolutionary events such as duplications, losses, transpositions, inversions, lateral transfers, and domain shuffling. We focus on the gene duplication event, that constitutes a major force in the creation of genes with new function [Ohno 1970; Lynch and Force 2000] and, thereby also, of biodiversity.<\/jats:p>\n          <jats:p>\n            We introduce the probabilistic\n            <jats:italic>gene evolution model<\/jats:italic>\n            , which describes how a gene tree evolves within a given species tree with respect to speciation, gene duplication, and gene loss. The actual relation between gene tree and species tree is captured by a reconciliation, a concept which we generalize for more expressiveness. The model is a canonical generalization of the classical linear birth-death process, obtained by replacing the interval where the process takes place by a tree.\n          <\/jats:p>\n          <jats:p>\n            For the\n            <jats:italic>gene evolution model<\/jats:italic>\n            , we derive efficient algorithms for some associated probability distributions: the probability of a reconciled tree, the probability of a gene tree, the maximum probability reconciliation, the posterior probability of a reconciliation, and sampling reconciliations with respect to the posterior probability. These algorithms provides the basis for several applications, including species tree construction, reconciliation analysis, orthology analysis, biogeography, and host-parasite co-evolution.\n          <\/jats:p>","DOI":"10.1145\/1502793.1502796","type":"journal-article","created":{"date-parts":[[2009,4,15]],"date-time":"2009-04-15T13:37:07Z","timestamp":1239802627000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":65,"title":["The gene evolution model and computing its associated probabilities"],"prefix":"10.1145","volume":"56","author":[{"given":"Lars","family":"Arvestad","sequence":"first","affiliation":[{"name":"Royal Institute of Technology and Stockholm Bioinformatics Center, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Lagergren","sequence":"additional","affiliation":[{"name":"Royal Institute of Technology and Stockholm Bioinformatics Center, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bengt","family":"Sennblad","sequence":"additional","affiliation":[{"name":"Stockholm University and Stockholm Bioinformatics Center, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,4,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720004000557"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btg1000"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/974614.974657"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1089\/106652701753216503"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2148-6-93"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.04.010"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM","author":"Bergeron A.","year":"2004","unstructured":"Bergeron , A. , Mixtacki , J. , and Stoye , J . 2004. Reversal distance without hurdles and fortresses. In Lecture Notes in Computer Science , Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004 ). Springer-Verlag, Berlin, Germany, 388--399. Bergeron, A., Mixtacki, J., and Stoye, J. 2004. Reversal distance without hurdles and fortresses. In Lecture Notes in Computer Science, Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004). Springer-Verlag, Berlin, Germany, 388--399."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Algorithms: 10th Annual European Symposium on Algorithms (ESA","author":"Berman P.","year":"2000","unstructured":"Berman , P. , Hannenhalli , S. , and Karpinski , M . 2002. 1.375-approximation algorithm for sorting by reversals. In Lecture Notes in Computer Science , Proceedings of the Algorithms: 10th Annual European Symposium on Algorithms (ESA 2000 ). Springer-Verlag, Berlin, Germany, 200--210. Berman, P., Hannenhalli, S., and Karpinski, M. 2002. 1.375-approximation algorithm for sorting by reversals. In Lecture Notes in Computer Science, Proceedings of the Algorithms: 10th Annual European Symposium on Algorithms (ESA 2000). Springer-Verlag, Berlin, Germany, 200--210."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ecolsys.33.010802.150511"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/43.1.78"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/42.3.384"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019731994X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Cheng Z. Ventura M. She X. Khaitovich P. Graves T. Osoegawa K. Church D. DeJong P. Wilson R. Pbo S. Rocchi M. and Eichler E. E. 2005. A genome-wide comparison of recent chimpanzee and human segmental duplications. Nature 437 7055 88--93.  Cheng Z. Ventura M. She X. Khaitovich P. Graves T. Osoegawa K. Church D. DeJong P. Wilson R. Pbo S. Rocchi M. and Eichler E. E. 2005. A genome-wide comparison of recent chimpanzee and human segmental duplications. Nature 437 7055 88--93.","DOI":"10.1038\/nature04000"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11415770_23"},{"key":"e_1_2_1_15_1","unstructured":"Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11732990_18"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/10635150390218277"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.0014-3820.2005.tb00891.x"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstb.2002.1185"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01734359"},{"key":"e_1_2_1_21_1","volume-title":"Inferring phylogenies","author":"Felsenstein J.","unstructured":"Felsenstein , J. 2003. Inferring phylogenies . Sinauer Associates . Felsenstein, J. 2003. Inferring phylogenies. Sinauer Associates."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2412448"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2148-6-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrmicro1204"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.2307\/2412519"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Hafner M. S. Sudman P. D. Villablanca F. X. Spradling T. A. Demastes J. W. and Nadler S. A. 1994. Disparate rates of molecular evolution in cospeciating hosts and parasites. Science 265 5175 1087--1090.  Hafner M. S. Sudman P. D. Villablanca F. X. Spradling T. A. Demastes J. W. and Nadler S. A. 1994. Disparate rates of molecular evolution in cospeciating hosts and parasites. Science 265 5175 1087--1090.","DOI":"10.1126\/science.8066445"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.3567505"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300516"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/1426329"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1558-5646.1983.tb05528.x"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1558-5646.1997.tb02428.x"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.8.754"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Jeffroy O. Brinkmann H. Delsuc F. and Philippe H. 2006. Phylogenomics: the beginning of incongruence&quest; Trends Genet. 22 4 225--231.  Jeffroy O. Brinkmann H. Delsuc F. and Philippe H. 2006. Phylogenomics: the beginning of incongruence&quest; Trends Genet. 22 4 225--231.","DOI":"10.1016\/j.tig.2006.02.003"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177730285"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a026160"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1080\/10635150701429982"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1093\/genetics\/154.1.459","article-title":"The probability of duplicate gene preservation by subfunctionalization","volume":"154","author":"Lynch M.","year":"2000","unstructured":"Lynch , M. , and Force , A. 2000 . The probability of duplicate gene preservation by subfunctionalization . Genetics 154 , 1, 459 -- 473 . Lynch, M., and Force, A. 2000. The probability of duplicate gene preservation by subfunctionalization. Genetics 154, 1, 459--473.","journal-title":"Genetics"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2148-3-2"},{"key":"e_1_2_1_40_1","article-title":"The reconstructed evolutionary process","volume":"344","author":"Nee S.","year":"1994","unstructured":"Nee , S. , May , R. M. , and Harvey , P. H. 1994 . The reconstructed evolutionary process . Philos. Trans. Roy. Soc. London, B. Biol. Sci. 344 , 1309, 305--311. Nee, S., May, R. M., and Harvey, P. H. 1994. The reconstructed evolutionary process. Philos. Trans. Roy. Soc. London, B. Biol. Sci. 344, 1309, 305--311.","journal-title":"Philos. Trans. Roy. Soc. London, B. Biol. Sci."},{"key":"e_1_2_1_41_1","unstructured":"Nelson G. and Platnick N. I. 1981. Systematics and biogeography: Cladistics and vicariance. Columbia University Press New York.  Nelson G. and Platnick N. I. 1981. Systematics and biogeography: Cladistics and vicariance. Columbia University Press New York."},{"key":"e_1_2_1_42_1","volume-title":"Evolution by Gene Duplication","author":"Ohno S.","unstructured":"Ohno , S. 1970. Evolution by Gene Duplication . Springer-Verlag , Berlin, Germany . Ohno, S. 1970. Evolution by Gene Duplication. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_43_1","first-page":"58","article-title":"Maps between trees and cladistic-analysis of historical associations among genes, organisms, and areas","volume":"43","author":"Page R. D. M.","year":"1994","unstructured":"Page , R. D. M. 1994 . Maps between trees and cladistic-analysis of historical associations among genes, organisms, and areas . Syst. Biol. 43 , 1, 58 -- 77 . Page, R. D. M. 1994. Maps between trees and cladistic-analysis of historical associations among genes, organisms, and areas. Syst. Biol. 43, 1, 58--77.","journal-title":"Syst. Biol."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/mpev.1996.0390"},{"key":"e_1_2_1_45_1","volume-title":"BIOCOMPUTING 2002: Proceedings of the Pacific Symposium. World Scientific Publishing, 536--547","author":"Page R. D.","year":"2002","unstructured":"Page , R. D. , Cotton , J. A. 2002 . Vertebrate phylogenomics: reconciled trees and gene duplications . In BIOCOMPUTING 2002: Proceedings of the Pacific Symposium. World Scientific Publishing, 536--547 . Page, R. D., Cotton, J. A. 2002. Vertebrate phylogenomics: reconciled trees and gene duplications. In BIOCOMPUTING 2002: Proceedings of the Pacific Symposium. World Scientific Publishing, 536--547."},{"key":"e_1_2_1_46_1","first-page":"568","article-title":"Relationships between gene trees and species trees","volume":"5","author":"Pamilo P.","year":"1988","unstructured":"Pamilo , P. , and Nei , M. 1988 . Relationships between gene trees and species trees . Mol. Biol. Evol. 5 , 5, 568 -- 583 . Pamilo, P., and Nei, M. 1988. Relationships between gene trees and species trees. Mol. Biol. Evol. 5, 5, 568--583.","journal-title":"Mol. Biol. Evol."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.13.351"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","first-page":"1645","DOI":"10.1093\/genetics\/164.4.1645","article-title":"Bayes estimation of species divergence times and ancestral population sizes using DNA sequences from multiple loci","volume":"164","author":"Rannala B.","year":"2003","unstructured":"Rannala , B. , and Yang , Z. 2003 . Bayes estimation of species divergence times and ancestral population sizes using DNA sequences from multiple loci . Genetics 164 , 4, 1645 -- 1656 . Rannala, B., and Yang, Z. 2003. Bayes estimation of species divergence times and ancestral population sizes using DNA sequences from multiple loci. Genetics 164, 4, 1645--1656.","journal-title":"Genetics"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.2000.5197"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00239-004-0175-8"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Rokas A. Williams B. L. King N. and Carroll S. B. 2003. Genome-scale approaches to resolving incongruence in molecular phylogenies. Nature 425 6960 798--804.  Rokas A. Williams B. L. King N. and Carroll S. B. 2003. Genome-scale approaches to resolving incongruence in molecular phylogenies. Nature 425 6960 798--804.","DOI":"10.1038\/nature02053"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.1.92"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr1305203"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.212646199"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1096-0031.2001.tb00109.x"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1093\/genetics\/105.2.437","article-title":"Evolutionary relationship of DNA sequences in finite populations","volume":"105","author":"Tajima F.","year":"1983","unstructured":"Tajima , F. 1983 . Evolutionary relationship of DNA sequences in finite populations . Genetics 105 , 2, 437 -- 460 . Tajima, F. 1983. Evolutionary relationship of DNA sequences in finite populations. Genetics 105, 2, 437--460.","journal-title":"Genetics"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM","author":"Tannier E.","year":"2004","unstructured":"Tannier , E. , and Sagot , M . -F. 2004. Sorting by reversals in subquadratic time. In Lecture Notes in Computer Science , Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004 ). Springer-Verlag, Berlin, Germany, 1--13. Tannier, E., and Sagot, M.-F. 2004. Sorting by reversals in subquadratic time. In Lecture Notes in Computer Science, Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004). Springer-Verlag, Berlin, Germany, 1--13."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.278.5338.631"},{"key":"e_1_2_1_59_1","volume-title":"Human Evolutionary Trees","author":"Thompson E. A.","unstructured":"Thompson , E. A. 1975. Human Evolutionary Trees . Cambridge University Press , Cambridge . Thompson, E. A. 1975. Human Evolutionary Trees. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a025811"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/14.3.285"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-3-14"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502796","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1502793.1502796","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:37Z","timestamp":1750253377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1502793.1502796"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1502793.1502796"],"URL":"https:\/\/doi.org\/10.1145\/1502793.1502796","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2006-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}