<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue1" %>
Unique Solvability of Certain Hybrid Networks from their Distances
Stephen J. Willson
Department of Mathematics, Iowa State University, Ames, IA 50011, USA
Annals of Combinatorics 10 (1) p.165-178 March, 2006
AMS Subject Classification: 92D15, 05C20
Phylogenetic relationships among taxa have usually been represented by rooted trees in which the leaves correspond to extant taxa and interior vertices correspond to extinct ancestral taxa. Recently, more general graphs than trees have been investigated in order to be able to represent hybridization, lateral gene transfer, and recombination events. A model is presented in which the genome at a vertex is represented by a binary string. In the presence of hybridization and the absence of convergent evolution and homoplasies, the evolution is modeled by an acyclic digraph. It is shown how distances are most naturally related to the vertices rather than to the edges. Indeed, distances are computed in terms of the "originating weights" at vertices. It is shown that some distances may not in fact correspond to the sum of branch lengths on any path in the graph. In typical applications, direct measurements can be made only on the leaves, including the root. A study is made of how to infer the originating weights at interior vertices from such information.
Keywords: phylogenetic network, phylogenetic tree, directed graph, hybridization, hybrid


1. D. Gusfield, Efficient algorithms for inferring evolutionary history, Networks 21 (1991) 19--28.

2. D. Gusfield, S. Eddhu, and C. Langley, Optimal, efficient reconstruction of phylogenetic networks with constrained recombination, J. Bioinform. Comput. Biol. 2 (2004) 173--213.

3. D. Gusfield, S. Eddhu, and C. Langley, The fine structure of galls in phylogenetic networks, INFORMS J. Comput. 16 (2004) 459--469.

4. M. Hall, Jr., Combinatorial Theory, 2nd Ed., John Wiley & Sons, New York, 1986.

5. M. Hasegawa, H. Kishino, and K. Yano, Dating of the human-ape splitting by a molecular clock of mitochondrial DNA, J. Mol. Evol. 22 (1985) 160--174.

6. J. Hein, Reconstructing evolution of sequences subject to recombination using parsimony, Math. Biosci. 98 (1990) 185--200.

7. J. Hein, A heuristic method to reconstruct the history of sequences subject to recombination, J. Mol. Evol. 36 (1993) 396--405.

8. K.T. Huber, M. Langton, D. Penny, V. Moulton, and M.Hendy, Spectronet: a package for computing spectra and median networks, Appl. Bioinformatics 1 (3) (2002) 159--161.

9. D.H. Huson, SplitsTree: a program for analyzing and visualizing evolutionary data, Bioinformatics 141 (1998) 68--73.

10. T.H. Jukes and C.R. Cantor, Evolution of protein molecules, In: Evolution of Life: Fossils, Molecules, and Culture, S. Osawa and T. Honjo, Eds., Springer-Verlag, Tokyo, (1969) 79--95.

11. M. Kimura, A simple method for estimating evolutionary rate of base substitutions through comparative studies of nucleotide sequences, J. Mol. Evol. 16 (1980) 111--120.

12. V. Makarenkov, T-REX: reconstructing and visualizing phylogenetic trees and reticulation networks, Bioinformatics 17 (2001) 664--668.

13. V. Makarenkov and P. Legendre, From a phylogenetic tree to a reticulated network, J. Comput. Biol. 11 (2004) 195--212.

14. C. Semple and M. Steel, Phylogenetics, Oxford University Press, Oxford, 2003.

15. L. Wang, K. Zhang, and L. Zhang, Perfect phylogenetic networks with recombination, J. Comput. Biol. 8 (2001) 69--78.