Title :
Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem
Author :
Nguyen, C. Thach ; Nguyen, Nguyen Bao ; Sung, Wing-Kin ; Zhang, Louxin
Author_Institution :
Nat. Uni. of Singapore, Singapore
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 proven NP-hard even for galled recombination networks. A dynamic programming algorithm is also developed to solve the small parsimony problem. It takes O(dn23 h ) time on an input recombination network over length-d sequences in which there are h recombination and n -h tree nodes.
Keywords :
biology computing; genetics; polynomials; dynamic programming; phylogenetic trees; polynomial-time solvable; recombination network reconstruction; sequence data; small parsimony problem; Bioinformatics; Dynamic programming; Genetic mutations; Genomics; Heuristic algorithms; Microorganisms; Organisms; Phylogeny; Polynomials; Sequences; NP-hardness; approximability; combination network; dynamic programming; parsimony method; phylogenetic network; Algorithms; Base Sequence; Computer Simulation; DNA Mutational Analysis; Evolution, Molecular; Models, Genetic; Molecular Sequence Data; Phylogeny; Recombination, Genetic; Sequence Analysis, DNA; Signal Transduction; Variation (Genetics);
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/tcbb.2007.1018
