skip to main content
article

Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem

Published: 01 July 2007 Publication History

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.

References

[1]
G. Bourque and L.X. Zhang, “Models and Methods in Comparative Genomics,” Advances in Computer Science, vol. 68, pp. 59-104, 2006.
[2]
C. Choy, J. Jansson, K. Sadakane, and W.-K. Sung, “Computing the Maximum Agreement of Phylogenetic Networks,” Theoretical Computer Science, vol. 335, pp. 93-107, 2005.
[3]
W.F. Doolittle, “Phylogenetic Classification and the Universal Tree,” Science, vol. 284, pp. 2124-2129, 1999.
[4]
W.M. Fitch, “Toward Defining the Course of Evolution: Minimum Change for Specific Tree Topology,” J. Zoological System, vol. 20, pp. 406-416, 1971.
[5]
D. Gusfield and V. Bansal, “A Fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters,” Proc. RECOMB '05, pp. 217-232, 2005.
[6]
D. Gusfield, S. Eddhu, and C. Langley, “Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination,” J. Bioinformatics and Computational Biology, vol. 2, no. 1, pp. 173-213, 2004.
[7]
D. Gusfield, S. Eddhu, and C. Langley, “The Fine Structure of Galls in Phylogenetic Networks,” Informs J. Computing, vol. 16, no. 4, pp. 459-469, 2004.
[8]
J. Hein, “Reconstructing the History of Sequences Subject to Gene Conversion and Recombination,” Math. Bioscience, vol. 98, pp. 185-200, 1990.
[9]
J. Hein, “A Heuristic Method to Reconstruct the History of Sequences Subject to Recombination,” J. Molecular Evolution, vol. 20, pp. 402-411, 1993.
[10]
J. Huang, N. Mullapudi, T. Sicheritz-Ponten, and J.C. Kissinger, “A First Glimpse into the Pattern and Scale of Gene Transfer in Apicomplexa,” Int'l J. Parasitology, vol. 34, no. 3, pp. 265-74, 2004.
[11]
D.H. Huson et al., “Reconstruction of Reticulate Networks from Gene Trees,” Lecture Notes in Computer Science vol. 3500, pp. 233-249, 2005.
[12]
D.H. Huson, T. Dezulian, T. Klopper, and M. Steel, “Phylogenetic Super-Networks from Partial Trees,” IEEE Trans. Computational Biology and Bioinformatics, vol. 1, pp. 151-158, 2004.
[13]
D.H. Huson and T.H. Kloepper, “Computing Recombination Networks from Binary Sequences,” Bioinformatics, vol. 21, supplement ii, pp. ii159-ii165, 2005.
[14]
T.N.D. Huynh, J. Jansson, N.B. Nguyen, and W.-K. Sung, “Constructing a Smallest Refining Galled Phylogenetic Network,” Lecture Notes in Computer Science, vol. 3500, pp. 265-280, 2005.
[15]
J. Jansson, N.B. Nguyen, and W.-K. Sung, “Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network,” Proc. ACM-SIAM Symp. Discrete Algorithms (SODA '05), pp. 349-358, 2005.
[16]
J.G. Lawrence and H. Ochman, “Reconciling the Many Faces of Lateral Gene Transfer,” Trends Microbiology, vol. 10, pp. 1-4, 2002.
[17]
D.A. Morrison, “Networks in Phylogenetic Analysis: New Tools for Population Biology,” Int'l J. Parasitology, vol. 35, no. 5, pp. 567-82, 2005.
[18]
L. Nakhleh et al., “Reconstructing Phylogenetic Networks Using Maximum Parsimony,” Proc. 2005 IEEE Computational Systems Bioinformatics Conf., pp. 93-102, 2005.
[19]
L. Nakhleh et al., “Reconstructing Reticulate Evolution in Species —Theory and Practice,” J. Computational Biology, vol. 12, pp. 796-811, 2005.
[20]
K.E. Nelson et al., “Evidence for Lateral Gene Transfer between Archaea and Bacteria from Genome Sequence of Thermotoga Maritima,” Nature, vol. 27, pp. 323-329, 1999.
[21]
M. Nordborg and S. Tavaré, “Linkage Disequilibrium: What History Has to Tell Us,” Trends in Genetics, vol. 18, pp. 83-90, 2002.
[22]
L.S. Wang, K.Z. Zhang, and L.X. Zhang, “Perfect Phylogenetic Networks with Recombination,” J. Computational Biology, vol. 8, no. 1, pp. 69-78, 2001.

Cited By

View all
  • (2009)Parsimony Score of Phylogenetic NetworksIEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)10.1109/TCBB.2008.1196:3(495-505)Online publication date: 1-Jul-2009
  • (2007)A new linear-time heuristic algorithm for computing the parsimony score of phylogenetic networksProceedings of the 3rd international conference on Bioinformatics research and applications10.5555/1759681.1759687(61-72)Online publication date: 7-May-2007

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics
IEEE/ACM Transactions on Computational Biology and Bioinformatics  Volume 4, Issue 3
July 2007
192 pages

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 July 2007
Published in TCBB Volume 4, Issue 3

Author Tags

  1. NP-hardness
  2. approximability
  3. combination network
  4. dynamic programming
  5. parsimony method
  6. phylogenetic network

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)1
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2009)Parsimony Score of Phylogenetic NetworksIEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)10.1109/TCBB.2008.1196:3(495-505)Online publication date: 1-Jul-2009
  • (2007)A new linear-time heuristic algorithm for computing the parsimony score of phylogenetic networksProceedings of the 3rd international conference on Bioinformatics research and applications10.5555/1759681.1759687(61-72)Online publication date: 7-May-2007

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media