title: Genomic duplication problems for unrooted gene trees.
abstract: BACKGROUND
  Discovering the location of gene duplications and multiple gene duplication episodes is a fundamental issue in evolutionary molecular biology. The problem introduced by Guigó et al. in 1996 is to map gene duplication events from a collection of rooted, binary gene family trees onto theirs corresponding rooted binary species tree in such a way that the total number of multiple gene duplication episodes is minimized. There are several models in the literature that specify how gene duplications from gene families can be interpreted as one duplication episode. However, in all duplication episode problems gene trees are rooted. This restriction limits the applicability, since unrooted gene family trees are frequently inferred by phylogenetic methods.
  
  
  RESULTS
  In this article we show the first solution to the open problem of episode clustering where the input gene family trees are unrooted. In particular, by using theoretical properties of unrooted reconciliation, we show an efficient algorithm that reduces this problem into the episode clustering problems defined for rooted trees. We show theoretical properties of the reduction algorithm and evaluation of empirical datasets.
  
  
  CONCLUSIONS
  We provided algorithms and tools that were successfully applied to several empirical datasets. In particular, our comparative study shows that we can improve known results on genomic duplication inference from real datasets.
authors.affiliation: University of Warsaw, Institute of Informatics, Banacha 2, Warsaw, 02-097, Poland. jpaszek@mimuw.edu.pl.
authors.forename: Jarosław
authors.initials: J
authors.lastname: Paszek
authors.affiliation: University of Warsaw, Institute of Informatics, Banacha 2, Warsaw, 02-097, Poland. gorecki@mimuw.edu.pl.
authors.forename: Paweł
authors.initials: P
authors.lastname: Górecki
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D030541:Databases, Genetic; D020440:Gene Duplication / Q000235:genetics*; D008957:Models, Genetic
references.citation: Bioinformatics. 2007 Jan 15;23(2):e116-22
references.pmid: 17237078
references.citation: Bioinformatics. 2003;19 Suppl 1:i7-15
references.pmid: 12855432
references.citation: Genome. 2004 Jun;47(3):610-4
references.pmid: 15190378
references.citation: Nucleic Acids Res. 2008 Jan;36(Database issue):D735-40
references.pmid: 18056084
references.citation: Pac Symp Biocomput. 2002;:536-47
references.pmid: 11928506
references.citation: Genome Res. 2006 Jun;16(6):738-49
references.pmid: 16702410
references.citation: Mol Phylogenet Evol. 1996 Oct;6(2):189-213
references.pmid: 8899723
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2011 Nov-Dec;8(6):1685-91
references.pmid: 21576759
references.citation: Syst Biol. 2002 Feb;51(1):32-43
references.pmid: 11943091
references.citation: Bioinformatics. 2008 Jul 1;24(13):i132-8
references.pmid: 18586705
references.citation: Syst Biol. 2014 May;63(3):409-20
references.pmid: 24562812
references.citation: J Bioinform Comput Biol. 2013 Oct;11(5):1342005
references.pmid: 24131054
references.citation: Nature. 2004 Apr 8;428(6983):617-24
references.pmid: 15004568
references.citation: BMC Bioinformatics. 2012 Jun 25;13 Suppl 10:S14
references.pmid: 22759419
references.citation: Trends Genet. 2006 Jul;22(7):375-87
references.pmid: 16730849
references.citation: Syst Biol. 2003 Apr;52(2):229-38
references.pmid: 12746148
references.citation: Bioinformatics. 2012 Sep 15;28(18):i409-i415
references.pmid: 22962460
references.citation: J Comput Biol. 2009 Oct;16(10):1399-418
references.pmid: 19754270
references.citation: Nature. 2006 Nov 9;444(7116):171-8
references.pmid: 17086204
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2013 Mar-Apr;10(2):522-36
references.pmid: 23929875
references.citation: Science. 2000 Dec 15;290(5499):2114-7
references.pmid: 11118139
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2011 Jan-Mar;8(1):260-5
references.pmid: 21071814
references.citation: Mol Phylogenet Evol. 2000 Jan;14(1):89-106
references.pmid: 10631044
references.citation: Nucleic Acids Res. 2009 Jan;37(Database issue):D550-4
references.pmid: 19015150
references.citation: J Comput Biol. 2006 Mar;13(2):320-35
references.pmid: 16597243
references.citation: Nat Rev Genet. 2009 Oct;10(10):725-32
references.pmid: 19652647
references.citation: Science. 2014 Jan 3;343(6166):88-91
references.pmid: 24310611
references.citation: J Comput Biol. 1995 Winter;2(4):493-507
references.pmid: 8634901