Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms, SIAM J. Comput, vol.26, pp.1656-1669, 1997. ,
Building trees, hunting for trees, and comparing trees, 1997. ,
The size of a maximum agreement subtree for random binary trees, Dimacs Series in Discrete Mathematics and Theoretical Computer Science, vol.61, pp.55-66, 2003. ,
New results on optimizing rooted triplets consistency, Discrete Appl. Math, vol.158, pp.1136-1147, 2010. ,
URL : https://hal.archives-ouvertes.fr/hal-00824940
Computing a consensus phylogeny via leaf removal, International Symposium on Bioinformatics Research and Applications, pp.3-15, 2019. ,
An O(nlog n) algorithm for the maximum agreement subtree problem for binary trees, SIAM J. Comput, vol.30, pp.1385-1404, 2000. ,
Fast Compatibility Testing for Rooted Phylogenetic Trees, Combinatorial Pattern Matching, vol.54, p.12, 2016. ,
Fixed-parameter algorithms for finding agreement supertrees, SIAM J. Comput, vol.44, pp.384-410, 2015. ,
Algorithms on strings, trees and sequences: computer science and computational biology, 1997. ,
, Phylogenomics with paralogs. Proc. Natl. Acad. Sci. USA, vol.112, pp.2058-2063, 2015.
Whole-genome analyses resolve early branches in the tree of life of modern birds, Science, vol.346, pp.1320-1331, 2014. ,
URL : https://hal.archives-ouvertes.fr/hal-02046801
Incomplete lineage sorting in mammalian phylogenomics, Sys. Biol, vol.66, pp.112-120, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01815360
Joint amalgamation of most parsimonious reconciled gene trees, Bioinformatics, vol.31, pp.841-848, 2015. ,
URL : https://hal.archives-ouvertes.fr/hal-02154935
Phylogenetic modeling of lateral gene transfer reconstructs the pattern and relative timing of speciations, Proc. Natl. Acad. Sci. USA, vol.109, pp.17513-17518, 2012. ,
FastRFS: fast and accurate robinson-foulds supertrees using constrained exact optimization, Bioinformatics, vol.33, pp.631-639, 2017. ,
, We have shown above that for any T ? P * , x is descended from y T in T and not from z T for any z ? Z, and so x ? L T (y T ) \ z ?Z L T (z T ). As |L T m (z) \ z ?Z 1 L T m (z ))| ? 4(d + d ) and |(L T m (y) \ L T m (z)) \ y ?Z 2 L T m (y ))| ? 4(d + d ), we have |L T m (y) \ z ?Z L T m (z ))| ? 8(d + d ). To analyze the complexity, vol.63, pp.566-581, 2014.
, Note that T ?{x} = T ?X m = T m . Therefore u T is well-defined for every node u ? V (T m ), and every node in T is equal to u T for some u ? V (T m ), except for x and its parent in T . So let w be the parent of x in T , u T the parent of w in T , and v T the child of w in T that is not x. Observe that T can be obtained from T m by grafting x onto the arc uv. Then it is enough to show that uv ? F . To see that uv ? F , first note that for each z ? {y}?Z, z T is well-defined and (z T ) T = z T of y, and v is an ancestor of (L Tm (y) \ z ?Z L Tm (z ))) ? z ?Z z, L Tm (y) \ z?Z L Tm (z )) ? Z. As |L Tm (y)\ z ?Z L Tm (z )| ? 8(d+d ), |Z| ? 4 and T m is a binary tree, we have |F | ? 16(d+d )+8. For each e ? F , let T e be the tree obtained from T m by grafting x onto the arc e . Let P = {T e : e ? F }. Let T be a tree in P * and consider T = T ?(X m \{x})
, d, d ? 1) 14: if T is not F ALSE, let T * := T 15: Return T *