Topological Rearrangements and Local Search Method for Tandem Duplication Trees

摘要

The problem of reconstructing the duplication history of a set of tandemly repeated sequences was first introduced by Fitch (1977). Many recent works deal with this problem, showing the validity of the unequal recombination model proposed by Fitch, describing numerous inference algorithms, and exploring the combinatorial properties of these new mathematical objects, which are duplication trees (DT). In this paper, we deal with the topological rearrangement of these trees. Classical rearrangements used in phylogeny (NNI, SPR, TBR, ...) cannot be applied directly on DT. We demonstrate that restricting the neighborhood defined by the SPR (Subtree Pruning and Re-grafting) rearrangement to valid duplication trees, allows exploring the whole space of DT. We use these restricted rearrangements in a local search method which improves an initial tree via successive rearrangements and optimizes the parsimony criterion. We show through simulations that this method improves all existing programs for both reconstructing the initial tree and recovering its duplication events.