Blog
About

61
views
0
recommends
+1 Recommend
0 collections
    4
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We present efficient algorithms for computing a maximum agreement forest (MAF) of a pair of multifurcating (nonbinary) rooted trees. Our algorithms match the running times of the currently best algorithms for the binary case. The size of an MAF corresponds to the subtree prune-and-regraft (SPR) distance of the two trees and is intimately connected to their hybridization number. These distance measures are essential tools for understanding reticulate evolution, such as lateral gene transfer, recombination, and hybridization. Multifurcating trees arise naturally as a result of statistical uncertainty in current tree construction methods.

          Related collections

          Most cited references 12

          • Record: found
          • Abstract: not found
          • Article: not found

          Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            RECONSTRUCTING CHARACTER EVOLUTION ON POLYTOMOUS CLADOGRAMS

              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found

              Horizontal transfer of a virulence operon to the ancestor of Mycobacterium tuberculosis.

              The contribution of interspecies horizontal gene transfer (HGT) to the evolution and virulence of Mycobacterium tuberculosis, the agent of tuberculosis in humans, has been barely investigated. Here we have studied the evolutionary history of the M. tuberculosis Rv0986-8 virulence operon recently identified, through functional genomics approaches, as playing an important role in parasitism of host phagocytic cells. We showed that among actinobacteria, this operon is specific to the M. tuberculosis complex and to ancestral Mycobacterium prototuberculosis species. These data, together with phylogenetic reconstruction and other in silico analyses, provided strong evidence that this operon has been acquired horizontally by the ancestor of M. tuberculosis, before the recent evolutionary bottleneck that preceded the clonal-like evolution of the M. tuberculosis complex. Genomic signature profiling further suggested that the transfer was plasmid mediated and that the operon originated from a gamma-proteobacterium donor species. Our study points out for the first time the contribution of HGT to the emergence of M. tuberculosis and close relatives as major pathogens. In addition, our data underline the importance of deciphering gene transfer networks in M. tuberculosis in order to better understand the evolutionary mechanisms involved in mycobacterial virulence.
                Bookmark

                Author and article information

                Journal
                1305.0512

                Evolutionary Biology, Data structures & Algorithms

                Comments

                Comment on this article