#### DMCA

## An approximation algorithm for computing a parsimonious first speciation in the gene duplication model (2010)

Citations: | 4 - 2 self |

### Citations

79 | A supertree method for rooted trees
- Semple, Steel
- 2000
(Show Context)
Citation Context ...r supertree problems, greedy heuristics based on the principle of computing successive optimal speciations, modeled as edge-cuts in a graph whose vertices are the considered species, are now standard =-=[18,21]-=-. In such heuristics, each Minimum Edge-Cut splits the set of considered species into two subsets that correspond to a speciation that results in two distinct lineages. Computing an optimal first spec... |

75 | Zhang L: From gene trees to species trees
- Ma, Li
(Show Context)
Citation Context ...ads to the following optimization problem called the Minimum Duplication Problem (MD Problem): given a gene tree forest F find a species tree S such that d(F, S) is minimum. The MD Problem is NP-hard =-=[16]-=-, even in the case where every gene tree is a uniquely leaf labeled and rooted triplet [4], in which case it is in fact equivalent to Fig. 1. AgenetreeT and a species tree S on a set of genome G = {1,... |

64 | A Simple Combinatorial Algorithm for Submodular Function Minimization
- Iwata, Orlin
- 2009
(Show Context)
Citation Context ...combinatorial optimization problems have been linked to submodular functions [10], in particular the MEC Problem. Given a submodular function f, the following optimization problem, which is tractable =-=[14]-=-, is a special case of the Set Function Minimization Problem: Submodular Function Minimization (SFM) Problem: Input: A submodular function f :2V → R with ground set V ; Output: A non-empty subset X of... |

57 | New algorithms for the duplication-loss model.
- Hallett, Lagergren
- 2000
(Show Context)
Citation Context ...elieved ten years ago [22] — but also that it cannot be approximated within a constant ratio unless P=NP [6]. Hence, for solving the MD Problem, one has to rely on exponential time algorithms such as =-=[13]-=- or local-search methods with no optimality guarantee [1,25]. In [7], it was shown that the MD Problem is in fact a slight variant of a supertree problem (see also [20] that explores the link between ... |

53 |
Modified mincut supertrees
- Page
- 2002
(Show Context)
Citation Context ...r supertree problems, greedy heuristics based on the principle of computing successive optimal speciations, modeled as edge-cuts in a graph whose vertices are the considered species, are now standard =-=[18,21]-=-. In such heuristics, each Minimum Edge-Cut splits the set of considered species into two subsets that correspond to a speciation that results in two distinct lineages. Computing an optimal first spec... |

38 | Inferring angiosperm phylogeny from EST data with widespread gene duplication.,
- Sanderson, McMahon
- 2007
(Show Context)
Citation Context ...his algorithm on both synthetic and real data. 1 Introduction Gene duplication is a fundamental evolutionary mechanism for important groups of eukaryotes such as vertebrates [3], insects [15], plants =-=[19]-=- or fungi [23]. Gene duplications, together with gene losses, result in gene families, whichcancontain several copies of a same gene in a given genome. Recent advances in methods for reconstructing ph... |

37 |
Tiuryn J: DLS-trees: a model of evolutionary scenarios
- Gorecki
(Show Context)
Citation Context ...ion. Inferring parsimonious species trees and speciations. It is well known that d(F, S) is the minimum number of gene duplication events required in any evolutionary scenario that resulted in F (see =-=[7,11]-=- and references there), which leads to the following optimization problem called the Minimum Duplication Problem (MD Problem): given a gene tree forest F find a species tree S such that d(F, S) is min... |

37 | Gene family evolution across 12 drosophila genomes. PLoS Genet 3:e197
- Hahn, Han, et al.
- 2007
(Show Context)
Citation Context ...otential of this algorithm on both synthetic and real data. 1 Introduction Gene duplication is a fundamental evolutionary mechanism for important groups of eukaryotes such as vertebrates [3], insects =-=[15]-=-, plants [19] or fungi [23]. Gene duplications, together with gene losses, result in gene families, whichcancontain several copies of a same gene in a given genome. Recent advances in methods for reco... |

28 | El-Mabrouk N: New perspectives on gene family evolution: losses in reconciliation and a link with supertrees
- Chauve
- 2009
(Show Context)
Citation Context ...earch heuristics proved to be useful [1] and have been applied on several eukaryotic datasets with interesting results (see [19,25]), but with no optimality guarantee. Recently, Chauve and El-Mabrouk =-=[7,20]-=- described a formal link between the Minimum Duplication Problem and a problem of supertrees, where, given a set of uniquely leaf-labeled gene trees (there is at most one copy of each gene in E. Tanni... |

28 | The gain and loss of genes during 600 million years of vertebrate evolution. - Blomme, Vandepoele, et al. - 2006 |

18 | Gene trees and species trees: The gene-duplication problem is fixedparameter tractable - Stege - 1999 |

15 |
Hunting for trees, building trees and comparing trees: theory and method in phylogenetic analysis
- Bryant
- 1997
(Show Context)
Citation Context ...nimum number of gene trees [6]. This problem — a version of the MD Problem restricted to uniquely leaf-labeled trees — is NP-hard too, even in the simple case where each gene tree is a rooted triplet =-=[4]-=-. For supertree problems, greedy heuristics based on the principle of computing successive optimal speciations, modeled as edge-cuts in a graph whose vertices are the considered species, are now stand... |

13 | New results on optimizing rooted triplets consistency
- Byrka, Guillemot, et al.
- 2008
(Show Context)
Citation Context ...p. 290–301, 2010. c○ Springer-Verlag Berlin Heidelberg 2010An Approximation Algorithm 291 each genome), the goal is to reconstruct a species tree that disagrees with the minimum number of gene trees =-=[6]-=-. This problem — a version of the MD Problem restricted to uniquely leaf-labeled trees — is NP-hard too, even in the simple case where each gene tree is a rooted triplet [4]. For supertree problems, g... |

10 |
et al: TreeFam: a curated database of phylogenetic trees of animal gene families
- Li, Coghlan, et al.
(Show Context)
Citation Context ... given genome. Recent advances in methods for reconstructing phylogenetic trees for individual gene families, have resulted in large sets of accurate gene trees for eukaryote species, such as TreeFam =-=[24]-=-. Phylogenomics aims at reconstructing the evolution of species (genomes) by inferring a species tree for the set of genomes from a set of gene trees. The Minimum Duplication Problem (MD Problem), als... |

7 | A note on the fixed parameter tractability of the geneduplication problem
- Bansal, Shamir
- 2010
(Show Context)
Citation Context ...es tree that induces an evolutionary history with a minimum number of gene duplications. This problem is NP-hard, and is neither fixed-parameter tractable (FPT) nor approximable with a constant ratio =-=[2,12]-=-. Recent advances in local search heuristics proved to be useful [1] and have been applied on several eukaryotic datasets with interesting results (see [19,25]), but with no optimality guarantee. Rece... |

4 |
Approches combinatoires pour le consensus d’arbres et de séquences, Thèse de l’Université de Montpellier
- GUILLEMOT
- 2008
(Show Context)
Citation Context ...es tree that induces an evolutionary history with a minimum number of gene duplications. This problem is NP-hard, and is neither fixed-parameter tractable (FPT) nor approximable with a constant ratio =-=[2,12]-=-. Recent advances in local search heuristics proved to be useful [1] and have been applied on several eukaryotic datasets with interesting results (see [19,25]), but with no optimality guarantee. Rece... |

3 |
Faster min-cut computation in unweighted hypergraphs/circuit netlists
- Mak
- 2005
(Show Context)
Citation Context ...)) is equal to the cardinality of EJh (B). Hence, the minimization of fJ can be reduced to the MHC Problem on Jh. The time complexity given in the theorem then follows from the algorithm described in =-=[17]-=- solving the MHC Problem on a hypergraph G in time and space O(kn) wherek (resp. n) isthe number of vertices (resp. hyperedges) of G. Additional remarks. If there exists at least one parsimonious firs... |

2 | A 3-approximation algorithm for computing a parsimonious first speciation in the gene duplication model. Available: arxiv.org/abs/0904.1645v2 - Chauve, Ouangraoua |

2 |
et al. CAFE: a computational tool for the study of gene family evolution. Bioinformatics 2006;22(10):1269–71
- Bie, Cristianini, et al.
(Show Context)
Citation Context ...t were studied in [7]; each dataset contains 100 gene trees. Each gene tree was generated from a single ancestral gene with duplication (birth) and loss (death) rates computed using the software CAFE =-=[9]-=- from real Drosophilia gene families [15]. To balance the fact that each gene tree originates from a single ancestral gene (and then has no duplication before the first speciation), and to consider da... |

2 |
Submodular Functions and Optimization, 2nd edn
- Fujishige
- 2005
(Show Context)
Citation Context ...ynomial time 2-approximation algorithm for the Minimum Duplication Bipartition Problem that generalizes the Minimum Edge-Cut approach used in supertrees and relies on Submodular Function Minimization =-=[10]-=-. Although our focus here is mostly theoretical, and explores the combinatorial structure of parsimonious first speciations, we also provide experimental results, on small datasets, which illustrate t... |

2 | V.: From gene trees to species trees through a supertree approach
- Scornavacca, Berry, et al.
- 2009
(Show Context)
Citation Context ...earch heuristics proved to be useful [1] and have been applied on several eukaryotic datasets with interesting results (see [19,25]), but with no optimality guarantee. Recently, Chauve and El-Mabrouk =-=[7,20]-=- described a formal link between the Minimum Duplication Problem and a problem of supertrees, where, given a set of uniquely leaf-labeled gene trees (there is at most one copy of each gene in E. Tanni... |

2 |
et al.: Natural history and evolutionary principles of gene duplication in fungi. Nature
- Wapinski
- 2007
(Show Context)
Citation Context ...on both synthetic and real data. 1 Introduction Gene duplication is a fundamental evolutionary mechanism for important groups of eukaryotes such as vertebrates [3], insects [15], plants [19] or fungi =-=[23]-=-. Gene duplications, together with gene losses, result in gene families, whichcancontain several copies of a same gene in a given genome. Recent advances in methods for reconstructing phylogenetic tre... |

2 | Ranwez 2009. From gene trees to species trees through a supertree approach - Scornavacca, Berry, et al. |

2 | Friedman N et al (2007) Natural history and evolutionary principles of gene duplication in fungi. Nature 449:54–61 - Wapinski, Pfeffer |

1 |
et al.. Heuristics for the gene-duplication problem: A Θ(n) speed-up for the local search
- Bansal
(Show Context)
Citation Context ...ene duplications. This problem is NP-hard, and is neither fixed-parameter tractable (FPT) nor approximable with a constant ratio [2,12]. Recent advances in local search heuristics proved to be useful =-=[1]-=- and have been applied on several eukaryotic datasets with interesting results (see [19,25]), but with no optimality guarantee. Recently, Chauve and El-Mabrouk [7,20] described a formal link between t... |

1 |
et al.: The gain and loss of genes during 600 millions years of vertebrate evolution
- Blomme, Peer
- 2006
(Show Context)
Citation Context ...ustrate the potential of this algorithm on both synthetic and real data. 1 Introduction Gene duplication is a fundamental evolutionary mechanism for important groups of eukaryotes such as vertebrates =-=[3]-=-, insects [15], plants [19] or fungi [23]. Gene duplications, together with gene losses, result in gene families, whichcancontain several copies of a same gene in a given genome. Recent advances in me... |

1 |
et al.: Genome-scale phylogenetics: Inferring the plant tree of life from 18,896 discordant gene trees Systematic Biology (in press
- Burleig
- 2010
(Show Context)
Citation Context ...essive parsimonious speciations and our approximation algorithm for computing such speciations are promising, and we plan to apply them on larger datasets, like those that will soon be available from =-=[5,26]-=-. From a theoretical point of view, the hardness of the Minimum Duplication Bipartition Problem is still an open problem, but we conjecture the problem is NP-complete. It is interesting to note that, ... |

1 |
et al.: DupTree: a program for large-scale phylogenetic analyses using gene tree parsimony
- Wehe
- 2008
(Show Context)
Citation Context ...T) nor approximable with a constant ratio [2,12]. Recent advances in local search heuristics proved to be useful [1] and have been applied on several eukaryotic datasets with interesting results (see =-=[19,25]-=-), but with no optimality guarantee. Recently, Chauve and El-Mabrouk [7,20] described a formal link between the Minimum Duplication Problem and a problem of supertrees, where, given a set of uniquely ... |

1 |
Phylogenetic detection of numerous gene duplications shared by animals, fungi and plants Genome Biol
- Zhou, Lin, et al.
- 2010
(Show Context)
Citation Context ...essive parsimonious speciations and our approximation algorithm for computing such speciations are promising, and we plan to apply them on larger datasets, like those that will soon be available from =-=[5,26]-=-. From a theoretical point of view, the hardness of the Minimum Duplication Bipartition Problem is still an open problem, but we conjecture the problem is NP-complete. It is interesting to note that, ... |

1 | Burleig et al.. 2010. Genome-scale phylogenetics: Inferring the plant tree of life from 18,896 discordant gene trees Systematic Biology - G |

1 | Bie et al.. 2006. CAFE: a computational tool for the study of gene family evolution - De |

1 | et al.. 2008. DupTree: a program for large-scale phylogenetic analyses using gene tree parsimony - Wehe |