Reconstructing recombination network from sequence data: the small parsimony problem

IEEE/ACM Trans Comput Biol Bioinform. 2007 Jul-Sep;4(3):394-402. doi: 10.1109/tcbb.2007.1018.

Abstract

The small parsimony problem is studied for reconstructing recombination networks from sequence data. The small parsimony problem is polynomial-time solvable for phylogenetic trees. However, the problem is proved NP-hard even for galled recombination networks. A dynamic programming algorithm is also developed to solve the small parsimony problem. It takes O(dn2(3h)) time on an input recombination network over length-d sequences in which there are h recombination and n - h tree nodes.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms*
  • Base Sequence
  • Computer Simulation
  • DNA Mutational Analysis / methods*
  • Evolution, Molecular*
  • Genetic Variation / genetics
  • Models, Genetic*
  • Molecular Sequence Data
  • Phylogeny
  • Recombination, Genetic / genetics*
  • Sequence Analysis, DNA / methods*
  • Signal Transduction / genetics*