IEEE ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS

Description

IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 1 Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem Sylvain Guillemot and Vincent Berry Abstract— Given a set L of labels and a collection of rooted trees whose leaves are bijectively labelled by some elements of L, the Maximum Agreement Supertree problem (SMAST) is as follows: find a tree T on a largest label set L? ? L that homeomorphically contains every input tree restricted to L?. The problem has phylogenetic applications to infer supertrees and perform tree congruence analyses. In this paper, we focus on the parameterized complexity of this NP-hard problem, considering different combinations of parameters as well as particular cases. We show that SMAST on k rooted binary trees on a label set of size n can be solved in O((8n)k) time, which is an improvement with respect to the previously known O(n3k2 ) time algorithm. In this case, we also give an O((2k)pkn2) time algorithm, where p is an upper bound on the number of leaves of L missing in a SMAST solution. This shows that SMAST can be solved efficiently when the input trees are mostly congruent. Then for the particular case where any triple of leaves is contained in at least one input tree, we give O(4pn3) and O(3.12p + n4) time algorithms, obtaining the first fixed-parameter tractable algorithms on a single parameter for this problem.

• smast can


• can only


• when such


• such rogue


• smast


• solving smast


• input trees


• agreement supertree

Sujets

• Guillemot

Informations

• Publié par: pefav
• Nombre de lectures: 13
• Langue: English

Extrait

IEEE/ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS

Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem Sylvain Guillemot and Vincent Berry

1

Abstract — Given a set L of labels and a collection of rooted trees, but sometimes result from a combination of more sourc e trees whose leaves are bijectively labelled by some elements trees which do not conict when considered pairwise. of L , the Maximum Agreement Supertree problem (S MAST ) is The most used supertree methods focus on clades, e.g., the as follows: nd a tree T on a largest label set L ′ ⊆ L that homeomorphically contains every input tree restricted to L ′ . The w m e e l t l h - o k d no [ w 3 n ],[ M 4] at a ri n x di R ts ep v r a e r s i e a n n t t a s t . io T n his w i i s th a P pr a o rs b i l m em ony wh ( en M e R ve P r ) problem has phylogenetic applications to infer supertrees and perform tree congruence analyses. the input trees contain some “rogue” taxa, i.e., labels whose In this paper, we focus on the parameterized complexity of position greatly differs from one input tree to another. Suc h rogue this NP -hard problem, considering different combinations of taxa can result from horizontal gene transfer (HGT) events [ 5], parameters as well as particular cases. We show that S MAST a phenomenon that commonly arises in bacteria, plants, and t o on k rooted binary trees on a label set of size n can be solved a lesser extent among vertebrates. The presence of rogue tax a in O ((8 n ) k ) time, which is an improvement with respect to the g p i r v e e vi a o n uslyknown 2 O ) ( t n 3 k 2 ) timealgorithm.In s th a is n c u a p s p e, er w b e o a u l n so d a c n a d ni h n e d n u c c e e h t a r v e e m a en n d o o n u - s ne c g h li a g n i g b e l s e i i n m t p h a e ct c i la n d t e he se s t u o p f er a tr n e i e n o p b u t t a t i re ne e d , O ((2 k ) p kn ime algorithm, where p i on the number of leaves of L missing in a S MAST solution. This ( b S y M c A la S d T e ) -b m as e e th d od m [ et 6 h ], od [ s 7 . ], T [8 h ] e ha M s ax b i e m en um spe A ci gr  e c e a m ll e y nt de S si u g p n e e rt d re t e o shows that S MAST can be solved efciently when the input trees are mostly congruent. Then for the particular case where any deal with rogue taxa: it infers a supertree from a set of sourc e triple of leaves is contained in at least one input tree, we give trees by removing some labels, i.e., taxa, on the position of which O (4 p n 3 ) and O (3  12 p + n 4 ) time algorithms, obtaining the rst the source tree a re xed-parameter tractable algorithms on a single parameter for s dis g e. More precisely, given a collecti on T of this problem. We also obtain intractability results for several s ro u o p t e e r d tre tr e e f e o s r w T it i h s l a ab tr e e ls e t T ak o e n n a in su a bs c e o t m L m ′ o ⊆ n s L et suc L h , t a h n at a e g a re c e h m tr e e n e t combinations of parameters, thus indicating that it is unlikely that xed-parameter tractable algorithms can be found in these of T restricted to L ′ is included in T . The computational problem particular cases. called S MAST , or sometimes M ASP [6], consists of nding an Index Terms — Phylogenetics, maximum agreement supertree, agreement supertree containing the maximum number of label s parameterized complexity, algorithms, reductions, rooted triples. fro T m he L . S MAST method, an extension of the i greement max mum a subtree method (M AST ), specically allows the input trees to I. I NTRODUCTION have different, and usually overlapping, label sets. With t his to re lac A. Motivation. p  ra e c x t i i b c i a li l ty a ,S l M ic A at S i T on i s s w w h e e ll r - e ad in a p pt u e t d treesh p ave e no M n-i A d S e T nti i c n a s l e l v a e b r e a l l pp Supertree construction consists of building trees on a larg e  sets. The rst such application is tree congruence analysis. Before set of labels from smaller trees covering parts of the label  building a supertree for a set of source trees, it is essentia l to set. This task is applied in bioinformatics where trees repr esent  certify that the source trees are not telling completely dif ferent phylogenies, but also in other elds such as databases [1] and data  stories on the evolution of studied taxa: if a set of source mining [2]. In phylogenetics, the tree nodes represent sequ ences  trees is not congruent enough, then no supertree can accurat ely or organisms ( taxa ), and the labels are bijectively associated with  represent the set. This can be problematic when subsequent the leaves of the trees, representing current organisms, wh ile  analyses have to be conducted from the supertree, e.g., meas uring internal nodes represent hypothetical ancestors. Rooted t rees are  the inuence of geographical or climate factors on speciation usually described by their set of clades : a clade is the set of labels  events. Several studies have recently proposed procedures to present under a same internal node. Clades represent relate d sets  assess the congruence of a set of source trees by randomizati on of organisms such as species, orders, families, etc. The goa l of  tests performed on M AST scores obtained for these trees: the supertree methods is to infer a tree that complies as closely as  source trees become more congruent as the number of leaves possible with the topological information of the source tre es. The  contained in their maximum agreement subtree increases [9] , [10], task is relatively easy when the input trees fully agree on th e  [11]. The study of [9] focuses on the case where the considere d relative positions of the labels. In this case, it is possibl e to nd,  source trees have different label sets and no taxon is common in polynomial time, a supertree that contains any input tree as  to all trees. They propose to divide the congruence analysis into an induced subtree [1], hence fully respecting the topologi cal  M AST computations on pairs of trees. The obtained values are information present in the data. However, practical input t rees  then normalized and summarized by an average value, for whic h usually conict with respect to the relative positioning of some  a p -value is computed by similar M AST computations on random labels. These incompatibilities sometimes affect only two input  trees. Here, replacing M AST with S MAST copes with the fact Manuscript submitted July 13, 2007 t a h n a a t ly i s n i put ca tr n ee b s e h p a e v rf e or di m ff e e d re d n i t re la ct b l e y l : s t e h t e s, w a h n o d l t e h s u e s t t o h f e t c re o e n s g c r a ue n nc b e e S. Guillemot and V. Berry are with the LIRMM, CNRS - University s Montpellier 2. Emails: { vberry,sguillem } @lirmm.fr considered at once, instead of resorting to separate analys es on