
Dan Gusfield,
Satish Eddhu and
Charles Langley. Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination. In JBCB, Vol. 2(1):173213, 2004. Keywords: explicit network, from sequences, galled tree, phylogenetic network, phylogeny, recombination, reconstruction. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/exfinalrec.pdf.
Toggle abstract
"A phylogenetic network is a generalization of a phylogenetic tree, allowing structural properties that are not treelike. In a seminal paper, Wang et al.1 studied the problem of constructing a phylogenetic network, allowing recombination between sequences, with the constraint that the resulting cycles must be disjoint. We call such a phylogenetic network a "galledtree". They gave a polynomialtime algorithm that was intended to determine whether or not a set of sequences could be generated on galledtree. Unfortunately, the algorithm by Wang et al.1 is incomplete and does not constitute a necessary test for the existence of a galledtree for the data. In this paper, we completely solve the problem. Moreover, we prove that if there is a galledtree, then the one produced by our algorithm minimizes the number of recombinations over all phylogenetic networks for the data, even allowing multiplecrossover recombinations. We also prove that when there is a galledtree for the data, the galledtree minimizing the number of recombinations is "essentially unique" . We. also note two additional results: first, any set of sequences that can be derived on a galled tree can be derived on a true tree (without recombination cycles), where at most one back mutation per site is allowed; second, the site compatibility problem (which is NPhard in general) can be solved in polynomial time for any set of sequences that can be derived on a galled tree. Perhaps more important than the specific results about galledtrees, we introduce an approach that can be used to study recombination in general phylogenetic networks. This paper greatly extends the conference version that appears in an earlier work.8 PowerPoint slides of the conference talk can be found at our website. © Imperial College Press."



Dan Gusfield,
Satish Eddhu and
Charles Langley. The fine structure of galls in phylogenetic networks. In INCOMP, Vol. 16(4):459469, 2004. Keywords: explicit network, from sequences, galled tree, phylogenetic network, phylogeny, reconstruction. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/informs.pdf.
Toggle abstract
"A phylogenetic network is a generalization of a phylogenetic tree, allowing properties that are not treelike. With the growth of genomic data, much of which does not fit ideal tree models, there is greater need to understand the algorithmics and combinatorics of phylogenetic networks (Posada and Crandall 2001, Schierup and Hein 2000). Wang et al. (2001) studied the problem of constructing a phylogenetic network for a set of n binary sequences derived from the allzero ancestral sequence, when each site in the sequence can mutate from zero to one at most once in the network, and recombination between sequences is allowed. They showed that the problem of minimizing the number of recombinations in such networks is NPhard, but introduced a special case of the problem, i.e., to determine whether the sequences could be derived on a phylogenetic network where the recombination cycles are nodedisjoint. Wang et al. (2001) provide a sufficient, but not a necessary test, for such solutions. Gusfield et al. (2003, 2004) gave a polynomialtime algorithm that is both a necessary and sufficient test. In this paper, we study in much more detail the fine combinatorial structure of nodedisjoint cycles in phylogenetic networks, both for purposes of insight into phylogenetic networks and to speed up parts of the previous algorithm. We explicitly characterize all the ways in which mutations can be arranged on a disjoint cycle, and prove a strong necessary condition for a set of mutations to be on a disjoint cycle. The main contribution here is to show how structure in the phylogenetic network is reflected in the structure of an efficientlycomputable graph, called the conflict graph. The success of this approach suggests that additional insight into the structure of phylogenetic networks can be obtained by exploring structural properties of the conflict graph."



Jesper Jansson and
WingKin Sung. Inferring a level1 phylogenetic network from a dense set of rooted triplets. In COCOON04, Vol. 3106:462471 of LNCS, springer, 2004. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/ipnrt6_COCOON2004.pdf.



Luay Nakhleh,
Tandy Warnow and
C. Randal Linder. Reconstructing reticulate evolution in species  theory and practice. In RECOMB04, Pages 337346, 2004. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/144nakhleh.pdf.



Mihaela Baroni. Hybrid phylogenies : a graphbased approach to represent reticulate evolution. PhD thesis, University of Canterbury, New Zealand, 2004. Keywords: explicit network, from rooted trees, galled tree, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, regular network. Note: http://ir.canterbury.ac.nz/bitstream/10092/4803/1/baroni_thesis.pdf.


