
Katharina Huber,
Michael Langton,
David Penny,
Vincent Moulton and
Mike Hendy. Spectronet: A package for computing spectra and median networks. In ABIO, Vol. 1(3):159161, 2004. Keywords: from splits, median network, phylogenetic network, phylogeny, Program Spectronet, software, split, visualization. Note: http://citeseer.ist.psu.edu/631776.html.
Toggle abstract
Spectronet is a package that uses various methods for exploring and visualising complex evolutionary signals. Given an alignment in NEXUS format, the package works by computing a collection of weighted splits or bipartitions of the taxa and then allows the user to interactively analyse the resulting collection using tools such as Lentoplots and median networks. The package is highly interactive and available for PCs.



Mihaela Baroni,
Charles Semple and
Mike Steel. A framework for representing reticulate evolution. In ACOM, Vol. 8:398401, 2004. Keywords: explicit network, from clusters, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, regular network, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BSS04.pdf.
Toggle abstract
"Acyclic directed graphs (ADGs) are increasingly being viewed as more appropriate for representing certain evolutionary relationships, particularly in biology, than rooted trees. In this paper, we develop a framework for the analysis of these graphs which we call hybrid phylogenies. We are particularly interested in the problem whereby one is given a set of phylogenetic trees and wishes to determine a hybrid phylogeny that 'embeds' each of these trees and which requires the smallest number of hybridisation events. We show that this quantity can be greatly reduced if additional species are involved, and investigate other combinatorial aspects of this and related questions."









Katharina Huber,
Vincent Moulton and
Charles Semple. Replacing cliques by stars in quasimedian graphs. In DAM, Vol. 143(13), 2004. Note: http://dx.doi.org/10.1016/j.dam.2004.03.002.
Toggle abstract
"For a multiset Σ of splits (bipartitions) of a finite set X, we introduce the multisplit graph G(Σ). This graph is a natural extension of the Buneman graph, Indeed, it is shown that several results pertaining to the Buneman graph extend to the multisplit graph. In addition, in case Σ is derived from a set ℛ of partitions of X by taking parts together with their complements, we show that the extremal instances where ℛ is either strongly compatible or strongly incompatible are equivalent to G(Σ) being either a tree or a Cartesian product of star trees, respectively. © 2004 Elsevier B.V. All rights reserved."



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."



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."





Yun S. Song and
Jotun Hein. On the Minimum Number of Recombination Events in the Evolutionary History of DNA Sequences. In JOMB, Vol. 48(2):160186, 2004. Keywords: minimum number, recombination. Note: http://dx.doi.org/10.1007/s0028500302275.
Toggle abstract
"In representing the evolutionary history of a set of binary DNA sequences by a connected graph, a set theoretical approach is introduced for studying recombination events. We show that set theoretical constraints have direct implications on the number of recombination events. We define a new lower bound on the number of recombination events and demonstrate the usefulness of our new approach through several explicit examples. © SpringerVerlag 2003."



David Bryant and
Vincent Moulton. NeighborNet: An Agglomerative Method for the Construction of Phylogenetic Networks. In MBE, Vol. 21(2):255265, 2004. Keywords: phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network. Note: http://www.math.auckland.ac.nz/~bryant/Papers/04NeighborNet.pdf.
Toggle abstract
"We present NeighborNet, a distance based method for constructing phylogenetic networks that is based on the NeighborJoining (NJ) algorithm of Saitou and Nei. NeighborNet provides a snapshot of the data that can guide more detailed analysis. Unlike split decomposition, NeighborNet scales well and can quickly produce detailed and informative networks for several hundred taxa. We illustrate the method by reanalyzing three published data sets: a collection of 110 highly recombinant Salmonella multilocus sequence typing sequences, the 135 "African Eve" human mitochondrial sequences published by Vigilant et al., and a collection of 12 Archeal chaperonin sequences demonstrating strong evidence for gene conversion. NeighborNet is available as part of the SplitsTree4 software package."





Bernard M. E. Moret,
Luay Nakhleh,
Tandy Warnow,
C. Randal Linder,
Anna Tholse,
Anneke Padolina,
Jerry Sun and
Ruth Timme. Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy. In TCBB, Vol. 1(1):1323, 2004. Keywords: distance between networks, evaluation, phylogenetic network, phylogeny, time consistent network, tripartition distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb04.pdf.



Vineet Bafna and
Vikas Bansal. The Number of Recombination Events in a Sample History: Conflict Graph and Lower Bounds. In TCBB, Vol. 1(2):7890, 2004. Keywords: ARG, bound, minimum number, phylogeny, recombination. Note: http://wwwcse.ucsd.edu/users/vbafna/pub/tcbb04.pdf.
Toggle abstract
"We consider the following problem: Given a set of binary sequences, determine lower bounds on the minimum number of recombinations required to explain the history of the sample, under the infinitesites model of mutation. The problem has implications for finding recombination hotspots and for the Ancestral Recombination Graph reconstruction problem. Hudson and Kaplan gave a lower bound based on the fourgamete test. In practice, their bound R m often greatly underestimates the minimum number of recombinations. The problem was recently revisited by Myers and Griffiths, who introduced two new lower bounds R h and R s which are provably better, and also yield good bounds in practice. However, the worstcase complexities of their procedures for computing R h and R s are exponential and superexponential, respectively. In this paper, we show that the number of nontrivial connected components, Rc, in the conflict graph for a given set of sequences, computable in time O(nm 2), is also a lower bound on the minimum number of recombination events. We show that in many cases, R c is a better bound than R h. The conflict graph was used by Gusfield et al. to obtain a polynomial time algorithm for the galled tree problem, which is a special case of the Ancestral Recombination Graph (ARG) reconstruction problem. Our results also offer some insight into the structural properties of this graph and are of interest for the general Ancestral Recombination Graph reconstruction problem."



Andreas W. M. Dress and
Daniel H. Huson. Constructing splits graphs. In TCBB, Vol. 1(3):109115, 2004. Keywords: abstract network, circular split system, from trees, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network, visualization. Note: http://scilib.kiev.ua/ieee/tcbb/2004/03/n3/n0109.pdf.
Toggle abstract
"Phylogenetic trees correspond onetoone to compatible systems of splits and so splits play an important role in theoretical and computational aspects of phylogeny. Whereas any tree reconstruction method can be thought of as producing a compatible system of splits, an increasing number of phylogenetlc algorithms are available that compute split systems that are not necessarily compatible and, thus, cannot always be represented by a tree. Such methods include the split decomposition, NeighborNet, consensus networks, and the Zclosure method. A more general split system of this kind can be represented graphically by a socalled splits graph, which generalizes the concept of a phylogenetic tree. This paper addresses the problem of computing a splits graph for a given set of splits. We have implemented all presented algorithms in a new program called SplitsTree4. © 2004 IEEE."



Daniel H. Huson,
Tobias Dezulian,
Tobias Kloepper and
Mike Steel. Phylogenetic SuperNetworks from Partial Trees. In TCBB, Vol. 1(4):151158, 2004. Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, supernetwork. Note: http://hdl.handle.net/10092/3177.
Toggle abstract
"In practice, one is often faced with incomplete phylogenetic data, such as a collection of partial trees or partial splits. This paper poses the problem of Inferring a phylogenetic supernetwork from such data and provides an efficient algorithm for doing so, called the Zclosure method. Additionally, the questions of assigning lengths to the edges of the network and how to restrict the "dimensionality" of the network are addressed. Applications to a set of five published partial gene trees relating different fungal species and to six published partial gene trees relating different grasses illustrate the usefulness of the method and an experimental study confirms Its potential. The method Is implemented as a plugin for the program SplitsTree4. © 2004 IEEE."







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.







Charles Choy,
Jesper Jansson,
Kunihiko Sadakane and
WingKin Sung. Computing the maximum agreement of phylogenetic networks. In Proceedings of Computing: the Tenth Australasian Theory Symposium (CATS'04), Vol. 91:134147 of Electronic Notes in Theoretical Computer Science, 2004. Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny. Note: http://www.df.lth.se/~jj/Publications/masn6_CATS2004.pdf.
Toggle abstract
"We introduce the maximum agreement phylogenetic subnetwork problem (MASN) of finding a branching structure shared by a set of phylogenetic networks. We prove that the problem is NPhard even if restricted to three phylogenetic networks and give an O(n2)time algorithm for the special case of two level1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a levelf phylogenetic network if every biconnected component in the underlying undirected graph contains at most f nodes having indegree 2 in N. Our algorithm can be extended to yield a polynomialtime algorithm for two levelf phylogenetic networks N 1,N2 for any f which is upperbounded by a constant; more precisely, its running time is O(V(N1)·V(N 2)·4f), where V(Ni) denotes the set of nodes of Ni. © 2004 Published by Elsevier B.V."





Pawel Górecki. Reconciliation problems for duplication, loss and horizontal gene transfer. In RECOMB04, Pages 316325, 2004. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://ai.stanford.edu/~serafim/CS374_2004/Papers/Gorecki_Reconciliation.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.



Mike Hallett,
Jens Lagergren and
Ali Tofigh. Simultaneous Identification of Duplications and Lateral Transfers. In RECOMB04, Pages 347356, 2004. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.nada.kth.se/~jensl/p164hallett.pdf.



