Reconstructing recombination network from sequence data: the small parsimony problem.
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.
C Thach
CT
Nguyen
Nguyen Bao
NB
Nguyen
Wing-Kin
WK
Sung
Louxin
L
Zhang
D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D004252:DNA Mutational Analysis / Q000379:methods*; D019143:Evolution, Molecular; D014644:Genetic Variation / Q000235:genetics; D008957:Models, Genetic; D008969:Molecular Sequence Data; D010802:Phylogeny; D011995:Recombination, Genetic / Q000235:genetics*; D017422:Sequence Analysis, DNA / Q000379:methods*; D015398:Signal Transduction / Q000235:genetics*