Reconstructing Recombination Network from Sequence Data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem

Full text

Pdf (305 KB)

Source

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) archive
Volume 4 , Issue 3 (July 2007) table of contents

Pages 394-402

Year of Publication: 2007

ISSN:1545-5963

Authors

C. Thach Nguyen
Nguyen Bao Nguyen
Wing-Kin Sung
Louxin Zhang

Publisher

IEEE Computer Society Press Los Alamitos, CA, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 80, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.