Who is Who in Phylogenetic Networks

All publications   ( Html | Bibtex | Both )   Order by:   Type | Year

Article (Journal)

1 Jean-Christophe Aude, Yolande Diaz-Lazcoz, Jean-Jacques Codani and Jean-Loup Risler. Applications of the Pyramidal Clustering Method to Biological Objects. In CC, Vol. 23(3-4):303-315, 1999. Keywords: from distances, phylogenetic network, phylogeny, Program Pyramids, pyramid, reconstruction, software, visualization. Note: http://dx.doi.org/10.1016/S0097-8485(99)00006-6.         @Article{ADCR1999,       AUTHOR = {Aude, Jean-Christophe and Diaz-Lazcoz, Yolande and Codani, Jean-Jacques and Risler, Jean-Loup},       TITLE = {Applications of the Pyramidal Clustering Method to Biological Objects},       YEAR = {1999},       JOURNAL = {CC},       VOLUME = {23},       NUMBER = {3-4},       PAGES = {303-315},       URL = {http://dx.doi.org/10.1016/S0097-8485(99)00006-6},       NOTE = {http://dx.doi.org/10.1016/S0097-8485(99)00006-6},       ANNOTE = {CITE : },       KEYWORDS = {from distances, phylogenetic network, phylogeny, Program Pyramids, pyramid, reconstruction, software, visualization} } 2 Vineet Bafna and Vikas Bansal. The Number of Recombination Events in a Sample History: Conflict Graph and Lower Bounds. In TCBB, Vol. 1(2):78-90, 2004. Keywords: ARG, bound, minimum number, phylogeny, recombination. Note: http://www-cse.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 infinite-sites 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 four-gamete 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 worst-case complexities of their procedures for computing R h and R s are exponential and super-exponential, 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." @Article{BafnaBansal2004,       AUTHOR = {Bafna, Vineet and Bansal, Vikas},       TITLE = {The Number of Recombination Events in a Sample History: Conflict Graph and Lower Bounds},       YEAR = {2004},       JOURNAL = {TCBB},       VOLUME = {1},       NUMBER = {2},       PAGES = {78-90},       URL = {http://dx.doi.org/10.1109/TCBB.2004.23},       NOTE = {http://www-cse.ucsd.edu/users/vbafna/pub/tcbb04.pdf},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {ARG, bound, minimum number, phylogeny, recombination} } 3 Hans-Jürgen Bandelt. Combination of data in phylogenetic analysis. In PSE, Vol. Supp. 9:336-361, 1995. Keywords: from trees, phylogenetic network, phylogeny, reconstruction.         @Article{Bandelt1995,       AUTHOR = {Bandelt, Hans-J{\~A}�rgen},       TITLE = {Combination of data in phylogenetic analysis},       YEAR = {1995},       JOURNAL = {PSE},       VOLUME = {Supp. 9},       PAGES = {336-361},       URL = {http://dx.doi.org/10.1007/978-3-7091-6612-3_38},       ANNOTE = {CITE : },       KEYWORDS = {from trees, phylogenetic network, phylogeny, reconstruction} } 4 Hans-Jürgen Bandelt and Andreas W. M. Dress. Weak hierarchies associated with similarity measures: an additive clustering technique. In BMB, Vol. 51:113-166, 1989. Keywords: abstract network, clustering, from distances, from trees, phylogenetic network, phylogeny, Program WeakHierarchies, reconstruction, weak hierarchy. Note: http://dx.doi.org/10.1007/BF02458841.         Toggle abstract "A new and apparently rather useful and natural concept in cluster analysis is studied: given a similarity measure on a set of objects, a sub-set is regarded as a cluster if any two objects a, b inside this sub-set have greater similarity than any third object outside has to at least one of a, b. These clusters then form a closure system which can be described as a hypergraph without triangles. Conversely, given such a system, one may attach some weight to each cluster and then compose a similarity measure additively, by letting the similarity of a pair be the sum of weights of the clusters containing that particular pair. The original clusters can be reconstructed from the obtained similarity measure. This clustering model is thus located between the general additive clustering model of Shepard and Arabie (1979) and the standard hierarchical model. Potential applications include fitting dendrograms with few additional nonnested clusters and simultaneous representation of some families of multiple dendrograms (in particular, two-dendrogram solutions), as well as assisting the search for phylogenetic relationships by proposing a somewhat larger system of possibly relevant "family groups", from which an appropriate choice (based on additional insight or individual preferences) remains to be made. © 1989 Society for Mathematical Biology." @Article{BandeltDress1989,       AUTHOR = {Bandelt, Hans-J{\~A}�rgen and Dress, Andreas W. M.},       TITLE = {Weak hierarchies associated with similarity measures: an additive clustering technique},       YEAR = {1989},       JOURNAL = {BMB},       VOLUME = {51},       PAGES = {113-166},       URL = {http://dx.doi.org/10.1007/BF02458841},       NOTE = {http://dx.doi.org/10.1007/BF02458841},       ANNOTE = {BIBUPDATE : 20070920},       KEYWORDS = {abstract network, clustering, from distances, from trees, phylogenetic network, phylogeny, Program WeakHierarchies, reconstruction, weak hierarchy} } 5 Hans-Jürgen Bandelt and Andreas W. M. Dress. A canonical decomposition theory for metrics on a finite set. In Advances in Mathematics, Vol. 92(1):47-105, 1992. Keywords: abstract network, circular split system, from distances, split, split decomposition, split network, weak hierarchy, weakly compatible.         Toggle abstract "We consider specific additive decompositions d = d1 + ... + dn of metrics, defined on a finite set X (where a metric may give distance zero to pairs of distinct points). The simplest building stones are the slit metrics, associated to splits (i.e., bipartitions) of the given set X. While an additive decomposition of a Hamming metric into split metrics is in no way unique, we achieve uniqueness by restricting ourselves to coherent decompositions, that is, decompositions d = d1 + ... + dn such that for every map f:X → R with f(x) + f(y) ≥ d(x, y) for all x, y ε{lunate} X there exist maps f1, ..., fn: X → R with f = f1 + ... + fn and fi(x) + fi(y) ≥ di(x, y) for all i = 1,..., n and all x, y ε{lunate} X. These coherent decompositions are closely related to a geometric decomposition of the injective hull of the given metric. A metric with a coherent decomposition into a (weighted) sum of split metrics will be called totally split-decomposable. Tree metrics (and more generally, the sum of two tree metrics) are particular instances of totally split-decomposable metrics. Our main result confirms that every metric admits a coherent decomposition into a totally split-decomposable metric and a split-prime residue, where all the split summands and hence the decomposition can be determined in polynomial time, and that a family of splits can occur this way if and only if it does not induce on any four-point subset all three splits with block size two. © 1992." @Article{BandeltDress1992,       AUTHOR = {Bandelt, Hans-J{\~A}�rgen and Dress, Andreas W. M.},       TITLE = {A canonical decomposition theory for metrics on a finite set},       YEAR = {1992},       JOURNAL = {Advances in Mathematics},       VOLUME = {92},       NUMBER = {1},       PAGES = {47-105},       URL = {http://dx.doi.org/10.1016/0001-8708(92)90061-O},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, circular split system, from distances, split, split decomposition, split network, weak hierarchy, weakly compatible} } 6 Hans-Jürgen Bandelt and Andreas W. M. Dress. Split Decomposition: A new and useful approach to phylogenetic analysis of distance data. In MPE, Vol. 1(3):242-252, 1992. Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction, split, split decomposition, split network. Note: http://dx.doi.org/10.1016/1055-7903(92)90021-8.         Toggle abstract "In order to analyze the structure inherent to a matrix of dissimilarities (such as evolutionary distances) we propose to use a new technique called split decomposition. This method accurately dissects the given dissimilarity measure as a sum of elementary "split" metrics plus a (small) residue. The split summands identify related groups which are susceptible to further interpretation when casted against the available biological information. Reanalysis of previously published ribosomal RNA data sets using split decomposition illustrate the potential of this approach. © 1992." @Article{BandeltDress1992b,       AUTHOR = {Bandelt, Hans-J{\~A}�rgen and Dress, Andreas W. M.},       TITLE = {Split Decomposition: A new and useful approach to phylogenetic analysis of distance data},       YEAR = {1992},       JOURNAL = {MPE},       VOLUME = {1},       NUMBER = {3},       PAGES = {242-252},       URL = {http://dx.doi.org/10.1016/1055-7903(92)90021-8},       NOTE = {http://dx.doi.org/10.1016/1055-7903(92)90021-8},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, from distances, phylogenetic network, phylogeny, reconstruction, split, split decomposition, split network} } 7 Hans-Jürgen Bandelt and Andreas W. M. Dress. An order theoretic framework for overlapping clustering. In DM, Vol. 136(1-3):21-37, 1994.         Toggle abstract "Cluster analysis deals with procedures which - given a finite collection X of objects together with some kind of local dissimilarity information - identify those subcollections C of objects from X, called clusters, which exhibit a comparatively low degree of internal dissimilarity. In this note we study arbitrary mappings φ which assign to each subcollection A ⊆ X of objects its internal degree of dissimilarity φ (A), subject only to the natural condition that A ⊆ B ⊆ X implies φ (A) ̌ φ (B), and we analyse on a rather abstract, purely order theoretic level how assumptions concerning the way such a mapping φ might be constructed from local data (that is, data involving only a few objects at a time) influence the degree of overlapping observed within the resulting family of clusters, - and vice versa. Hence, unlike previous order theoretic approaches to cluster analysis, we do not restrict our attention to nonoverlapping, hierarchical clustering. Instead, we regard a dissimilarity function φ as an arbitrary isotone mapping from a finite partially ordered set I - e.g. the set P(X) of all subsets A of a finite set X - into a (partially) ordered set R - e.g. the nonnegative real numbers - and we study the correspondence between the two subsets C(φ) and D(φ) of I, formed by the elements whose images are inaccessible from above and from below, respectively. While D(φ) constitutes the local data structure from which φ can be built up, C(φ) embodies the family of clusters associated with φ. Our results imply that in case I: = P(X) and R: = R≥0 one has # D ̌ n for all Dε{lunate}D(φ) and some fixed nε{lunate}N if and only if{A figure is presented} for all C0,..., Cnε{lunate}C(φ) if and only if this holds for all subsets C0,..., Cn ⊆ X, generalizing a well-known criterion for n-conformity of hypergraphs as well as corresponding results due to Batbedat, dealing with the case n = 2. © 1994." @Article{BandeltDress1994,       AUTHOR = {Bandelt, Hans-J{\~A}�rgen and Dress, Andreas W. M.},       TITLE = {An order theoretic framework for overlapping clustering},       YEAR = {1994},       JOURNAL = {DM},       VOLUME = {136},       NUMBER = {1-3},       PAGES = {21-37},       URL = {http://dx.doi.org/10.1016/0012-365X(94)00105-R},       ANNOTE = {CITE : } } 8 Sergey Bereg and Yuanyi Zhang. Phylogenetic Networks Based on the Molecular Clock Hypothesis. In TCBB, Vol. 3(4), 2006. Note: http://www.utdallas.edu/~yzhang/Homepage/Papers/prep-tcbb.pdf.         Toggle abstract A classical result in phylogenetic trees is that a binary phylogenetic tree adhering to the molecular clock hypothesis exists if and only if the matrix of distances between taxa is ultrametric. The ultrametric condition is very restrictive. In this paper we study phylogenetic networks that can be constructed assuming the molecular clock hypothesis. We characterize distance matrices that admit such networks for 3 and 4 taxa. We also design two algorithms for constructing networks optimizing the least-squares fit. @Article{BeregZhang2006,       AUTHOR = {Bereg, Sergey and Zhang, Yuanyi},       TITLE = {Phylogenetic Networks Based on the Molecular Clock Hypothesis},       YEAR = {2006},       JOURNAL = {TCBB},       VOLUME = {3},       NUMBER = {4},       URL = {http://dx.doi.org/10.1109/tcbb.2007.1043},       NOTE = {http://www.utdallas.edu/~yzhang/Homepage/Papers/prep-tcbb.pdf},       ANNOTE = {CITE : } } 9 Patrice Bertrand and Edwin Diday. A visual representation of the compatibility between an order and a dissimilarity index: the pyramids. In CSQ, Vol. 2:31-42, 1985. Keywords: pyramid.         @Article{BertrandDiday1985,       AUTHOR = {Bertrand, Patrice and Diday, Edwin},       TITLE = {A visual representation of the compatibility between an order and a dissimilarity index: the pyramids},       YEAR = {1985},       JOURNAL = {CSQ},       VOLUME = {2},       PAGES = {31-42},       ANNOTE = {CITE : },       KEYWORDS = {pyramid} } 10 Patrice Bertrand and Edwin Diday. Une généralisation des arbres hiérarchiques~: les représentations pyramidales. In Revue de Statistique Appliquée, Vol. 38(3):53-78, 1990. Note: http://www.numdam.org/item?id=RSA_1990__38_3_53_0.         @Article{BertrandDiday1990,       AUTHOR = {Bertrand, Patrice and Diday, Edwin},       TITLE = {Une g{\~A}�n{\~A}�ralisation des arbres hi{\~A}�rarchiques~: les repr{\~A}�sentations pyramidales},       YEAR = {1990},       JOURNAL = {Revue de Statistique Appliqu{\~A}�e},       VOLUME = {38},       NUMBER = {3},       PAGES = {53-78},       NOTE = {http://www.numdam.org/item?id=RSA_1990__38_3_53_0},       ANNOTE = {CITE : } } 11 Hans-Jürgen Bandelt, Peter Forster, Bryan C. Sykes and Martin Richards. Mitochondrial portraits of human population using median networks. In GEN, Vol. 141:743-753, 1995. Keywords: from splits, median network, population genetics, Program Spectronet, reconstruction, visualization. Note: http://www.genetics.org/cgi/content/abstract/141/2/743.         @Article{BFSR1995,       AUTHOR = {Bandelt, Hans-J{\~A}�rgen and Forster, Peter and Sykes, Bryan C. and Richards, Martin},       TITLE = {Mitochondrial portraits of human population using median networks},       YEAR = {1995},       JOURNAL = {GEN},       VOLUME = {141},       PAGES = {743-753},       URL = {http://www.ncbi.nlm.nih.gov/pubmed/8647407},       NOTE = {http://www.genetics.org/cgi/content/abstract/141/2/743},       ANNOTE = {CITE : },       KEYWORDS = {from splits, median network, population genetics, Program Spectronet, reconstruction, visualization} } 12 Hans-Jürgen Bandelt, Peter Forster and Arne Röhl. Median-joining networks for inferring intraspecies phylogenies. In MBE, Vol. 16(1):37-48, 1999. Keywords: from sequences, median network, MedianJoining, Program Network, reconstruction, software. Note: http://mbe.oxfordjournals.org/cgi/content/abstract/16/1/37.         @Article{BFR1999,       AUTHOR = {Bandelt, Hans-J{\~A}�rgen and Forster, Peter and R{\~A}�hl, Arne},       TITLE = {Median-joining networks for inferring intraspecies phylogenies},       YEAR = {1999},       JOURNAL = {MBE},       VOLUME = {16},       NUMBER = {1},       PAGES = {37-48},       URL = {http://www.ncbi.nlm.nih.gov/pubmed/10331250},       NOTE = {http://mbe.oxfordjournals.org/cgi/content/abstract/16/1/37},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {from sequences, median network, MedianJoining, Program Network, reconstruction, software} } 13 Mihaela Baroni, Stefan Grünewald, Vincent Moulton and Charles Semple. Bounding the number of hybridization events for a consistent evolutionary history. In JOMB, Vol. 51(2):171-182, 2005. Keywords: agreement forest, bound, explicit network, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BGMS05.pdf.         Toggle abstract "Evolutionary processes such as hybridisation, lateral gene transfer, and recombination are all key factors in shaping the structure of genes and genomes. However, since such processes are not always best represented by trees, there is now considerable interest in using more general networks instead. For example, in recent studies it has been shown that networks can be used to provide lower bounds on the number of recombination events and also for the number of lateral gene transfers that took place in the evolutionary history of a set of molecular sequences. In this paper we describe the theoretical performance of some related bounds that result when merging pairs of trees into networks. © Springer-Verlag 2005." @Article{BGMS2005,       AUTHOR = {Baroni, Mihaela and Gr{\~A}�newald, Stefan and Moulton, Vincent and Semple, Charles},       TITLE = {Bounding the number of hybridization events for a consistent evolutionary history},       YEAR = {2005},       JOURNAL = {JOMB},       VOLUME = {51},       NUMBER = {2},       PAGES = {171-182},       URL = {http://dx.doi.org/10.1007/s00285-005-0315-9},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/BGMS05.pdf},       ANNOTE = {CITE : },       KEYWORDS = {agreement forest, bound, explicit network, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, SPR distance} } 14 Jaroslaw Byrka, Pawel Gawrychowski, Katharina Huber and Steven Kelk. Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks. In Journal of Discrete Algorithms, Vol. 8(1):65-75, 2010. Keywords: approximation, explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/0710.3258.         Toggle abstract "The study of phylogenetic networks is of great interest to computational evolutionary biology and numerous different types of such structures are known. This article addresses the following question concerning rooted versions of phylogenetic networks. What is the maximum value of p ∈ [0, 1] such that for every input set T of rooted triplets, there exists some network N such that at least p | T | of the triplets are consistent with N? We call an algorithm that computes such a network (where p is maximum) worst-case optimal. Here we prove that the set containing all triplets (the full triplet set) in some sense defines p. Moreover, given a network N that obtains a fraction p′ for the full triplet set (for any p′), we show how to efficiently modify N to obtain a fraction ≥ p′ for any given triplet set T. We demonstrate the power of this insight by presenting a worst-case optimal result for level-1 phylogenetic networks improving considerably upon the 5/12 fraction obtained recently by Jansson, Nguyen and Sung. For level-2 phylogenetic networks we show that p ≥ 0.61. We emphasize that, because we are taking | T | as a (trivial) upper bound on the size of an optimal solution for each specific input T, the results in this article do not exclude the existence of approximation algorithms that achieve approximation ratio better than p. Finally, we note that all the results in this article also apply to weighted triplet sets. © 2009 Elsevier B.V. All rights reserved." @Article{BGHK2010,       AUTHOR = {Byrka, Jaroslaw and Gawrychowski, Pawel and Huber, Katharina and Kelk, Steven},       TITLE = {Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks},       YEAR = {2010},       JOURNAL = {Journal of Discrete Algorithms},       VOLUME = {8},       NUMBER = {1},       PAGES = {65-75},       URL = {http://dx.doi.org/10.1016/j.jda.2009.01.004},       NOTE = {http://arxiv.org/abs/0710.3258},       ANNOTE = {BIBUPDATE : 20080312},       KEYWORDS = {approximation, explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, reconstruction} } 15 Magnus Bordewich, Simone Linz, Katherine St. John and Charles Semple. A reduction algorithm for computing the hybridization number of two trees. In EBIO, Vol. 3:86-98, 2007. Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, Program HybridNumber. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BLSS07.pdf.         @Article{BLSS2007,       AUTHOR = {Bordewich, Magnus and Linz, Simone and St. John, Katherine and Semple, Charles},       TITLE = {A reduction algorithm for computing the hybridization number of two trees},       YEAR = {2007},       JOURNAL = {EBIO},       VOLUME = {3},       PAGES = {86-98},       URL = {http://www.ncbi.nlm.nih.gov/pubmed/19461978},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/BLSS07.pdf},       ANNOTE = {BIBUPDATE : 20070919},       KEYWORDS = {agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, Program HybridNumber} } 16 Hans-Jürgen Bandelt, Vincent Macaulay and Martin Richards. Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA. In MPE, Vol. 16:8-28, 2000. Keywords: from sequences, from splits, median network, phylogenetic network, phylogeny, reconstruction. Note: http://www.stats.gla.ac.uk/~vincent/papers/speedy.pdf.         Toggle abstract "Molecular data sets characterized by few phylogenetically informative characters with a broad spectrum of mutation rates, such as intraspecific control-region sequence variation of human mitochondrial DNA (mtDNA), can be usefully visualized in the form of median networks. Here we provide a step-by-step guide to the construction of such networks by hand. We improve upon a previously implemented algorithm by outlining an efficient parametrized strategy amenable to large data sets, greedy reduction, which makes it possible to reconstruct some of the confounding recurrent mutations. This entails some postprocessing as well, which assists in capturing more parsimonious solutions. To simplify the creation of the resulting network by hand, we describe a speedy approach to network construction, based on a careful planning of the processing order. A coalescent simulation tailored to human mtDNA variation in Eurasia testifies to the usefulness of reduced median networks, while highlighting notorious problems faced by all phylogenetic methods in this context. Finally, we discuss two case studies involving the comparison of characters in the two hypervariable segments of the human mtDNA control region in the light of the worldwide control-region sequence database, as well as additional restriction fragment length polymorphism information. We conclude that only a minority of the mutations that hit the second segment occur at sites that would have a mutation rate comparable to those at most sites in the first segment. Discarding the known 'noisy' sites of the second segment enhances the analysis. (C) 2000 Academic Press." @Article{BMR2000,       AUTHOR = {Bandelt, Hans-J{\~A}�rgen and Macaulay, Vincent and Richards, Martin},       TITLE = {Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA},       YEAR = {2000},       JOURNAL = {MPE},       VOLUME = {16},       PAGES = {8-28},       URL = {http://dx.doi.org/10.1006/mpev.2000.0792},       NOTE = {http://www.stats.gla.ac.uk/~vincent/papers/speedy.pdf},       ANNOTE = {CITE : },       KEYWORDS = {from sequences, from splits, median network, phylogenetic network, phylogeny, reconstruction} } 17 Magnus Bordewich and Charles Semple. On the computational complexity of the rooted subtree prune and regraft distance. In ACOM, Vol. 8:409-423, 2005. Keywords: agreement forest, from rooted trees, NP complete, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS04.pdf.         Toggle abstract "The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees." @Article{BordewichSemple2005,       AUTHOR = {Bordewich, Magnus and Semple, Charles},       TITLE = {On the computational complexity of the rooted subtree prune and regraft distance},       YEAR = {2005},       JOURNAL = {ACOM},       VOLUME = {8},       PAGES = {409-423},       URL = {http://dx.doi.org/10.1007/s00026-004-0229-z},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/BS04.pdf},       ANNOTE = {BIBUPDATE : 20070919},       KEYWORDS = {agreement forest, from rooted trees, NP complete, SPR distance} } 18 Magnus Bordewich and Charles Semple. Computing the minimum number of hybridization events for a consistent evolutionary history. In DAM, Vol. 155:914-918, 2007. Keywords: agreement forest, approximation, APX hard, explicit network, from rooted trees, hybridization, inapproximability, NP complete, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS06a.pdf.         @Article{BordewichSemple2007a,       AUTHOR = {Bordewich, Magnus and Semple, Charles},       TITLE = {Computing the minimum number of hybridization events for a consistent evolutionary history},       YEAR = {2007},       JOURNAL = {DAM},       VOLUME = {155},       PAGES = {914-918},       URL = {http://dx.doi.org/10.1016/j.dam.2006.08.008},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/BS06a.pdf},       ANNOTE = {BIBUPDATE : 20070919},       KEYWORDS = {agreement forest, approximation, APX hard, explicit network, from rooted trees, hybridization, inapproximability, NP complete, phylogenetic network, phylogeny, SPR distance} } 19 Magnus Bordewich and Charles Semple. Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable. In TCBB, Vol. 4(3):458-466, 2007. Keywords: FPT, hybridization. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/BS06b.pdf.         @Article{BordewichSemple2007b,       AUTHOR = {Bordewich, Magnus and Semple, Charles},       TITLE = {Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable},       YEAR = {2007},       JOURNAL = {TCBB},       VOLUME = {4},       NUMBER = {3},       PAGES = {458-466},       URL = {http://dx.doi.org/10.1016/j.dam.2006.08.008},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/BS06b.pdf},       ANNOTE = {BIBUPDATE : 20070919},       KEYWORDS = {FPT, hybridization} } 20 David Bryant. The Splits in the Neighborhood of a Tree. In ACOM, Vol. 8(1):1-11, 2004. Note: http://citeseer.ist.psu.edu/668699.html.         @Article{Bryant2004,       AUTHOR = {Bryant, David},       TITLE = {The Splits in the Neighborhood of a Tree},       YEAR = {2004},       JOURNAL = {ACOM},       VOLUME = {8},       NUMBER = {1},       PAGES = {1-11},       URL = {http://dx.doi.org/10.1007/s00026-004-0200-z},       NOTE = {http://citeseer.ist.psu.edu/668699.html},       ANNOTE = {BIBUPDATE : 20070905} } 21 David Bryant and Vincent Moulton. NeighborNet: An Agglomerative Method for the Construction of Phylogenetic Networks. In MBE, Vol. 21(2):255-265, 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 Neighbor-Net, a distance based method for constructing phylogenetic networks that is based on the Neighbor-Joining (NJ) algorithm of Saitou and Nei. Neighbor-Net provides a snapshot of the data that can guide more detailed analysis. Unlike split decomposition, Neighbor-Net 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 multi-locus 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. Neighbor-Net is available as part of the SplitsTree4 software package." @Article{BryantMoulton2004,       AUTHOR = {Bryant, David and Moulton, Vincent},       TITLE = {NeighborNet: An Agglomerative Method for the Construction of Phylogenetic Networks},       YEAR = {2004},       JOURNAL = {MBE},       VOLUME = {21},       NUMBER = {2},       PAGES = {255-265},       URL = {http://dx.doi.org/10.1093/molbev/msh018},       NOTE = {http://www.math.auckland.ac.nz/~bryant/Papers/04NeighborNet.pdf},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network} } 22 Mihaela Baroni, Charles Semple and Mike Steel. A framework for representing reticulate evolution. In ACOM, Vol. 8:398-401, 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." @Article{BSS2004,       AUTHOR = {Baroni, Mihaela and Semple, Charles and Steel, Mike},       TITLE = {A framework for representing reticulate evolution},       YEAR = {2004},       JOURNAL = {ACOM},       VOLUME = {8},       PAGES = {398-401},       URL = {http://dx.doi.org/10.1007/s00026-004-0228-0},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/BSS04.pdf},       ANNOTE = {ISSUE : 4},       KEYWORDS = {explicit network, from clusters, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction, regular network, SPR distance} } 23 Mihaela Baroni, Charles Semple and Mike Steel. Hybrids in Real Time. In Systematic Biology, Vol. 55(1):46-56, 2006. Keywords: agreement forest, from rooted trees, phylogenetic network, phylogeny, polynomial, reconstruction, time consistent network. Note: http://www.math.canterbury.ac.nz/~m.steel/Non_UC/files/research/hybrids.pdf.         Toggle abstract "We describe some new and recent results that allow for the analysis and representation of reticulate evolution by nontree networks. In particular, we (1) present a simple result to show that, despite the presence of reticulation, there is always a well-defined underlying tree that corresponds to those parts of life that do not have a history of reticulation; (2) describe and apply new theory for determining the smallest number of hybridization events required to explain conflicting gene trees; and (3) present a new algorithm to determine whether an arbitrary rooted network can be realized by contemporaneous reticulation events. We illustrate these results with examples. Copyright © Society of Systematic Biologists." @Article{BSS2006,       AUTHOR = {Baroni, Mihaela and Semple, Charles and Steel, Mike},       TITLE = {Hybrids in Real Time},       YEAR = {2006},       JOURNAL = {Systematic Biology},       VOLUME = {55},       NUMBER = {1},       PAGES = {46-56},       URL = {http://dx.doi.org/10.1080/10635150500431197},       NOTE = {http://www.math.canterbury.ac.nz/~m.steel/Non_UC/files/research/hybrids.pdf},       ANNOTE = {CITE : },       KEYWORDS = {agreement forest, from rooted trees, phylogenetic network, phylogeny, polynomial, reconstruction, time consistent network} } 24 Ho-Leung Chan, Jesper Jansson, Tak-Wah Lam and Siu-Ming Yiu. Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. In JBCB, Vol. 4(4):807-832, 2006. Keywords: explicit network, from distances, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/dist_ugn7_JBCB2006.pdf.         Toggle abstract "Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edge-weighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n2 log n)-time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M′ of M such that there exists an ultrametric galled network that satisfies M′ is NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e. where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it. © 2006 Imperial College Press." @Article{CJLY2006,       AUTHOR = {Chan, Ho-Leung and Jansson, Jesper and Lam, Tak-Wah and Yiu, Siu-Ming},       TITLE = {Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix},       YEAR = {2006},       JOURNAL = {JBCB},       VOLUME = {4},       NUMBER = {4},       PAGES = {807-832},       URL = {http://dx.doi.org/10.1142/S0219720006002211},       NOTE = {http://www.df.lth.se/~jj/Publications/dist_ugn7_JBCB2006.pdf},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, from distances, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction} } 25 Charles Choy, Jesper Jansson, Kunihiko Sadakane and Wing-Kin Sung. Computing the maximum agreement of phylogenetic networks. In TCS, Vol. 335(1):93-107, 2005. Keywords: dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny. Note: http://www.df.lth.se/~jj/Publications/masn8_TCS2005.pdf.         Toggle abstract "We introduce the maximum agreement phylogenetic subnetwork problem (MASN) for finding branching structure shared by a set of phylogenetic networks. We prove that the problem is NP-hard even if restricted to three phylogenetic networks and give an O(n2)-time algorithm for the special case of two level-1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a level-f phylogenetic network if every biconnected component in the underlying undirected graph induces a subgraph of N containing at most f nodes with indegree 2. We also show how to extend our technique to yield a polynomial-time algorithm for any two level-f phylogenetic networks N1,N2 satisfying f=O(logn); more precisely, its running time is O(|V(N1)|·|V(N2)|·2f1+f2), where V(Ni) and fi denote the set of nodes in Ni and the level of Ni, respectively, for i∈{1,2}. © 2005 Elsevier B.V. All rights reserved." @Article{CJSS2005,       AUTHOR = {Choy, Charles and Jansson, Jesper and Sadakane, Kunihiko and Sung, Wing-Kin},       TITLE = {Computing the maximum agreement of phylogenetic networks},       YEAR = {2005},       JOURNAL = {TCS},       VOLUME = {335},       NUMBER = {1},       PAGES = {93-107},       URL = {http://dx.doi.org/10.1016/j.tcs.2004.12.012},       NOTE = {http://www.df.lth.se/~jj/Publications/masn8_TCS2005.pdf},       ANNOTE = {CITE : },       KEYWORDS = {dynamic programming, FPT, level k phylogenetic network, MASN, NP complete, phylogenetic network, phylogeny} } 26 Mark Clement, David Posada and Keith A. Crandall. TCS: a computer program to estimate gene genealogies. In MOLE, Vol. 9:1657-1659, 2000. Keywords: from sequences, parsimony, phylogenetic network, phylogeny, Program TCS, reconstruction, software, statistical parsimony. Note: http://darwin.uvigo.es/download/papers/08.tcs00.pdf.         Toggle abstract [No abstract available] @Article{CPC2000,       AUTHOR = {Clement, Mark and Posada, David and Crandall, Keith A.},       TITLE = {TCS: a computer program to estimate gene genealogies},       YEAR = {2000},       JOURNAL = {MOLE},       VOLUME = {9},       PAGES = {1657-1659},       URL = {http://dx.doi.org/10.1046/j.1365-294x.2000.01020.x},       NOTE = {http://darwin.uvigo.es/download/papers/08.tcs00.pdf},       KEYWORDS = {from sequences, parsimony, phylogenetic network, phylogeny, Program TCS, reconstruction, software, statistical parsimony} } 27 Gabriel Cardona, Francesc Rosselló and Gabriel Valiente. Tripartitions do not always discriminate phylogenetic networks. In MBIO, Vol. 211(2):356-370, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, Program Bio PhyloNetwork, tree-child network, tripartition distance. Note: http://arxiv.org/abs/0707.2376, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/valiente/.         Toggle abstract "Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of non-treelike evolutionary events, like recombination, hybridization, or lateral gene transfer. In a recent series of papers devoted to the study of reconstructibility of phylogenetic networks, Moret, Nakhleh, Warnow and collaborators introduced the so-called tripartition metric for phylogenetic networks. In this paper we show that, in fact, this tripartition metric does not satisfy the separation axiom of distances (zero distance means isomorphism, or, in a more relaxed version, zero distance means indistinguishability in some specific sense) in any of the subclasses of phylogenetic networks where it is claimed to do so. We also present a subclass of phylogenetic networks whose members can be singled out by means of their sets of tripartitions (or even clusters), and hence where the latter can be used to define a meaningful metric. © 2007 Elsevier Inc. All rights reserved." @Article{CRV2008,       AUTHOR = {Cardona, Gabriel and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {Tripartitions do not always discriminate phylogenetic networks.},       YEAR = {2008},       JOURNAL = {MBIO},       VOLUME = {211},       NUMBER = {2},       PAGES = {356-370},       URL = {http://dx.doi.org/10.1016/j.mbs.2007.11.003},       NOTE = {http://arxiv.org/abs/0707.2376, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/valiente/},       ANNOTE = {BIBUPDATE : 20080516},       KEYWORDS = {distance between networks, phylogenetic network, phylogeny, Program Bio PhyloNetwork, tree-child network, tripartition distance} } 28 Gabriel Cardona, Francesc Rosselló and Gabriel Valiente. Comparison of tree-child phylogenetic networks. In TCBB, Vol. 6(4):552-569, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program Bio PhyloNetwork, Program PhyloNetwork, tree sibling network, tree-child network. Note: http://arxiv.org/abs/0708.3499.         Toggle abstract "Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical algorithms for reconstructing a phylogenetic network from a set of sequences, all attempts to endorse a class of phylogenetic networks (strictly extending the class of phylogenetic trees) with a well-founded distance measure have, to the best of our knowledge and with the only exception of the bipartition distance on regular networks, failed so far. In this paper, we present and study a new meaningful class of phylogenetic networks, called tree-child phylogenetic networks, and we provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors. We then use this representation to define a distance on this class that extends the well-known Robinson-Foulds distance for phylogenetic trees and to give an alignment method for pairs of networks in this class. Simple polynomial algorithms for reconstructing a tree-child phylogenetic network from its path multiplicity vectors, for computing the distance between two tree-child phylogenetic networks and for aligning a pair of tree-child phylogenetic networks, are provided. They have been implemented as a Perl package and a Java applet, which can be found at http://bioinfo.uib.es/~recerca/ phylonetworks/mudistance/. © 2009 IEEE." @Article{CRV2009,       AUTHOR = {Cardona, Gabriel and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {Comparison of tree-child phylogenetic networks},       YEAR = {2009},       JOURNAL = {TCBB},       VOLUME = {6},       NUMBER = {4},       PAGES = {552-569},       URL = {http://dx.doi.org/10.1109/TCBB.2007.70270},       NOTE = {http://arxiv.org/abs/0708.3499},       ANNOTE = {BIBUPDATE : 20070924},       KEYWORDS = {explicit network, phylogenetic network, phylogeny, Program Bio PhyloNetwork, Program PhyloNetwork, tree sibling network, tree-child network} } 29 Joaquin Dopazo, Andreas W. M. Dress and Arndt von Haeseler. Split decomposition: a new technique to analyse viral evolution. In PNAS, Vol. 90:10320-10324, 1993. Keywords: abstract network, phylogenetic network, phylogeny, split, split decomposition, split network, visualization. Note: http://dx.doi.org/10.1073/pnas.90.21.10320.         @Article{DDH1993,       AUTHOR = {Dopazo, Joaquin and Dress, Andreas W. M. and von Haeseler, Arndt},       TITLE = {Split decomposition: a new technique to analyse viral evolution},       YEAR = {1993},       JOURNAL = {PNAS},       VOLUME = {90},       PAGES = {10320-10324},       URL = {http://dx.doi.org/10.1073/pnas.90.21.10320},       NOTE = {http://dx.doi.org/10.1073/pnas.90.21.10320},       ANNOTE = {BIBUPDATE : 20070927},       KEYWORDS = {abstract network, phylogenetic network, phylogeny, split, split decomposition, split network, visualization} } 30 Andreas W. M. Dress, Daniel H. Huson and Vincent Moulton. Analyzing and visualizing distance data using SplitsTree. In DAM, Vol. 71(1):95-109, 1996. Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://bibiserv.techfak.uni-bielefeld.de/splits/splits.pdf.         @Article{DHM1996,       AUTHOR = {Dress, Andreas W. M. and Huson, Daniel H. and Moulton, Vincent},       TITLE = {Analyzing and visualizing distance data using SplitsTree},       YEAR = {1996},       JOURNAL = {DAM},       VOLUME = {71},       NUMBER = {1},       PAGES = {95-109},       URL = {http://dx.doi.org/10.1016/S0166-218X(96)00059-5},       NOTE = {http://bibiserv.techfak.uni-bielefeld.de/splits/splits.pdf},       ANNOTE = {BIBUPDATE : 20070927},       KEYWORDS = {abstract network, from distances, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization} } 31 Andreas W. M. Dress, Katharina Huber and Vincent Moulton. Some Variations on a Theme by Buneman. In ACOM, Vol. 1:339-352, 1997. Note: http://dx.doi.org/10.1007/BF02558485.         @Article{DHM1997,       AUTHOR = {Dress, Andreas W. M. and Huber, Katharina and Moulton, Vincent},       TITLE = {Some Variations on a Theme by Buneman},       YEAR = {1997},       JOURNAL = {ACOM},       VOLUME = {1},       PAGES = {339-352},       URL = {http://dx.doi.org/10.1007/BF02558485},       NOTE = {http://dx.doi.org/10.1007/BF02558485},       ANNOTE = {BIBUPDATE : 20070919} } 32 W. Ford Doolittle. Phylogenetic Classification and the Universal Tree. In Science, Vol. 284:2124-2128, 1999. Note: http://cas.bellarmine.edu/tietjen/Ecology/phylogenetic_classification_and_.htm.         Toggle abstract "From comparative analyses of the nucleotide sequences of genes encoding ribosornal RNAs and several proteins, molecular phylogeneticists have constructed a 'universal- tree of life,' taking it as the basis for a 'natural' hierarchical classification of all living things. Although confidence in some of the tree s early branches has recently been shaken, new approaches could still resolve many methodological uncertainties. More challenging is evidence that most archaeal and bacterial genomes (and the inferred ancestral eukaryotic nuclear genome) contain genes from multiple sources. If 'chimerism' or 'lateral gene transfer' cannot be dismissed as trivial in extent or limited to special categories of genes, then no hierarchical universal classification can be taken as natural. Molecular phylogeneticists will have failed to find the 'true tree,' not because their methods are inadequate or because they have chosen the wrong genes, but because the history of life cannot properly be represented as a tree. However, taxonomies based on molecular sequences will remain indispensable, and understanding of the evolutionary process will ultimately be enriched, not impoverished." @Article{Doolittle1999,       AUTHOR = {Doolittle, W. Ford},       TITLE = {Phylogenetic Classification and the Universal Tree},       YEAR = {1999},       JOURNAL = {Science},       VOLUME = {284},       PAGES = {2124-2128},       URL = {http://dx.doi.org/10.1126/science.284.5423.2124},       NOTE = {http://cas.bellarmine.edu/tietjen/Ecology/phylogenetic_classification_and_.htm},       ANNOTE = {CITE : } } 33 Andreas W. M. Dress and Daniel H. Huson. Constructing splits graphs. In TCBB, Vol. 1(3):109-115, 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 one-to-one 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, Neighbor-Net, consensus networks, and the Z-closure method. A more general split system of this kind can be represented graphically by a so-called 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." @Article{DressHuson2004,       AUTHOR = {Dress, Andreas W. M. and Huson, Daniel H.},       TITLE = {Constructing splits graphs},       YEAR = {2004},       JOURNAL = {TCBB},       VOLUME = {1},       NUMBER = {3},       PAGES = {109-115},       URL = {http://dx.doi.org/10.1109/TCBB.2004.27},       NOTE = {http://scilib.kiev.ua/ieee/tcbb/2004/03/n3/n0109.pdf},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, circular split system, from trees, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network, visualization} } 34 Walter M. Fitch. Networks and viral evolution. In JME, Vol. 44(Suppl. 1):S65-S75, 1997. Keywords: netting, parsimony, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1007/PL00000059.         @Article{Fitch1997,       AUTHOR = {Fitch, Walter M.},       TITLE = {Networks and viral evolution},       YEAR = {1997},       JOURNAL = {JME},       VOLUME = {44},       NUMBER = {Suppl. 1},       PAGES = {S65-S75},       URL = {http://dx.doi.org/10.1007/PL00000059},       NOTE = {http://dx.doi.org/10.1007/PL00000059},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {netting, parsimony, phylogenetic network, phylogeny, reconstruction} } 35 Philippe Gambette and Daniel H. Huson. Improved Layout of Phylogenetic Networks. In TCBB, Vol. 5(3):472-479, 2008. Keywords: abstract network, heuristic, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00309694/en/.         Toggle abstract "Split networks are increasingly being used in phylogenetic analysis. Usually, a simple equal-angle algorithm is used to draw such networks, producing layouts that leave much room for improvement. Addressing the problem of producing better layouts of split networks, this paper presents an algorithm for maximizing the area covered by the network, describes an extension of the equal-daylight algorithm to networks, looks into using a spring embedder, and discusses how to construct rooted split networks. © 2008 IEEE." @Article{GambetteHuson2008,       AUTHOR = {Gambette, Philippe and Huson, Daniel H.},       TITLE = {Improved Layout of Phylogenetic Networks},       YEAR = {2008},       JOURNAL = {TCBB},       VOLUME = {5},       NUMBER = {3},       PAGES = {472-479},       URL = {http://dx.doi.org/10.1109/TCBB.2007.1046},       NOTE = {http://hal-lirmm.ccsd.cnrs.fr/lirmm-00309694/en/},       ANNOTE = {BIBUPDATE : 20080301},       KEYWORDS = {abstract network, heuristic, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization} } 36 Olivier Gauthier and François-Joseph Lapointe. Hybrids and Phylogenetics Revisited: A Statistical Test of Hybridization Using Quartets. In Systematic Botany, Vol. 32(1):8-15, 2007. Keywords: explicit network, from quartets, hybridization, phylogenetic network, phylogeny, reconstruction, reticulogram, split decomposition. Note: http://dx.doi.org/10.1600/036364407780360238.         Toggle abstract "The occurrence of reticulations in the evolutionary history of species poses serious challenges for all modern practitioners of phylogenetic analysis. Such events, including hybridization, introgression, and lateral gene transfer, lead to evolutionary histories that cannot be adequately represented in the form of phylogenetic trees. Although numerous methods that allow for the reconstruction of phylogenetic networks have been proposed in recent years, the detection of reticulations still remains problematic. In this paper we present a Hybrid Detection Criterion (HDC) along with a statistical procedure that allows for the identification of hybrid taxa. The test assesses whether a putative hybrid is consistently intermediate between its postulated parents, with respect to the other taxa. The performance of the statistical method is evaluated using known hybrids of the genus Aphelandra (Acanthaceae) using two network methods: reticulograms and split decomposition graphs. Our results indicate that the HDC test is reliable when used jointly with split decomposition. On the other hand, the test lacks power and provides misleading results when using reticulograms. We then show how the procedure can be used as a tool to identify putative hybrids. © Copyright 2007 by the American Society of Plant Taxonomists." @Article{GauthierLapointe2007a,       AUTHOR = {Gauthier, Olivier and Lapointe, Fran{\~A}�ois-Joseph},       TITLE = {Hybrids and Phylogenetics Revisited: A Statistical Test of Hybridization Using Quartets},       YEAR = {2007},       JOURNAL = {Systematic Botany},       VOLUME = {32},       NUMBER = {1},       PAGES = {8-15},       URL = {http://dx.doi.org/10.1600/036364407780360238},       NOTE = {http://dx.doi.org/10.1600/036364407780360238},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, from quartets, hybridization, phylogenetic network, phylogeny, reconstruction, reticulogram, split decomposition} } 37 Olivier Gauthier and François-Joseph Lapointe. Seeing the Trees for the Network: Consensus, Information Content, and Superphylogenies. In Systematic Biology, Vol. 56(2):345-355, 2007. Keywords: consensus. Note: http://dx.doi.org/10.1080/10635150701286549.         Toggle abstract [No abstract available] @Article{GauthierLapointe2007b,       AUTHOR = {Gauthier, Olivier and Lapointe, Fran{\~A}�ois-Joseph},       TITLE = {Seeing the Trees for the Network: Consensus, Information Content, and Superphylogenies},       YEAR = {2007},       JOURNAL = {Systematic Biology},       VOLUME = {56},       NUMBER = {2},       PAGES = {345-355},       URL = {http://dx.doi.org/10.1080/10635150701286549},       NOTE = {http://dx.doi.org/10.1080/10635150701286549},       ANNOTE = {CITE : },       KEYWORDS = {consensus} } 38 Dan Gusfield, Satish Eddhu and Charles Langley. Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination. In JBCB, Vol. 2(1):173-213, 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 tree-like. 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 "galled-tree". They gave a polynomial-time algorithm that was intended to determine whether or not a set of sequences could be generated on galled-tree. Unfortunately, the algorithm by Wang et al.1 is incomplete and does not constitute a necessary test for the existence of a galled-tree for the data. In this paper, we completely solve the problem. Moreover, we prove that if there is a galled-tree, then the one produced by our algorithm minimizes the number of recombinations over all phylogenetic networks for the data, even allowing multiple-crossover recombinations. We also prove that when there is a galled-tree for the data, the galled-tree 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 NP-hard 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 galled-trees, 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." @Article{GEL2004b,       AUTHOR = {Gusfield, Dan and Eddhu, Satish and Langley, Charles},       TITLE = {Optimal, Efficient Reconstruction of Phylogenetic Networks with Constrained Recombination},       YEAR = {2004},       JOURNAL = {JBCB},       VOLUME = {2},       NUMBER = {1},       PAGES = {173-213},       URL = {http://dx.doi.org/10.1142/S0219720004000521},       NOTE = {http://wwwcsif.cs.ucdavis.edu/~gusfield/exfinalrec.pdf},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, from sequences, galled tree, phylogenetic network, phylogeny, recombination, reconstruction} } 39 Dan Gusfield, Satish Eddhu and Charles Langley. The fine structure of galls in phylogenetic networks. In INCOMP, Vol. 16(4):459-469, 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 tree-like. 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 all-zero 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 NP-hard, 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 node-disjoint. Wang et al. (2001) provide a sufficient, but not a necessary test, for such solutions. Gusfield et al. (2003, 2004) gave a polynomial-time algorithm that is both a necessary and sufficient test. In this paper, we study in much more detail the fine combinatorial structure of node-disjoint 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 efficiently-computable 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." @Article{GEL2004,       AUTHOR = {Gusfield, Dan and Eddhu, Satish and Langley, Charles},       TITLE = {The fine structure of galls in phylogenetic networks},       YEAR = {2004},       JOURNAL = {INCOMP},       VOLUME = {16},       NUMBER = {4},       PAGES = {459-469},       URL = {http://dx.doi.org/10.1287/ijoc.1040.0099},       NOTE = {http://wwwcsif.cs.ucdavis.edu/~gusfield/informs.pdf},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, from sequences, galled tree, phylogenetic network, phylogeny, reconstruction} } 40 Stefan Grünewald, Kristoffer Forslund, Andreas W. M. Dress and Vincent Moulton. QNet: An agglomerative method for the construction of phylogenetic networks from weighted quartets. In MBE, Vol. 24(2):532-538, 2007. Keywords: abstract network, circular split system, from quartets, phylogenetic network, phylogeny, Program QNet, reconstruction, software. Note: http://mbe.oxfordjournals.org/cgi/content/abstract/24/2/532.         Toggle abstract "We present QNet, a method for constructing split networks from weighted quartet trees. QNet can be viewed as a quartet analogue of the distance-based Neighbor-Net (NNet) method for network construction. Just as NNet, QNet works by agglomeratively computing a collection of circular weighted splits of the taxa set which is subsequently represented by a planar split network. To illustrate the applicability of QNet, we apply it to a previously published Salmonella data set. We conclude that QNet can provide a useful alternative to NNet if distance data are not available or a character-based approach is preferred. Moreover, it can be used as an aid for determining when a quartet-based tree-building method may or may not be appropriate for a given data set. QNet is freely available for download. © The Author 2006. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved." @Article{GFDM2007,       AUTHOR = {Gr{\~A}�newald, Stefan and Forslund, Kristoffer and Dress, Andreas W. M. and Moulton, Vincent},       TITLE = {QNet: An agglomerative method for the construction of phylogenetic networks from weighted quartets},       YEAR = {2007},       JOURNAL = {MBE},       VOLUME = {24},       NUMBER = {2},       PAGES = {532-538},       URL = {http://dx.doi.org/10.1093/molbev/msl180},       NOTE = {http://mbe.oxfordjournals.org/cgi/content/abstract/24/2/532},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, circular split system, from quartets, phylogenetic network, phylogeny, Program QNet, reconstruction, software} } 41 Dan Gusfield, Dean Hickerson and Satish Eddhu. An efficiently computed lower bound on the number of recombinations in phylogenetic networks: Theory and empirical study. In DAM, Vol. 155(6-7):806-830, 2007. Note: http://wwwcsif.cs.ucdavis.edu/~gusfield/cclowerbound.pdf.         Toggle abstract "Phylogenetic networks are models of sequence evolution that go beyond trees, allowing biological operations that are not tree-like. One of the most important biological operations is recombination between two sequences. An established problem [J. Hein, Reconstructing evolution of sequences subject to recombination using parsimony, Math. Biosci. 98 (1990) 185-200; J. Hein, A heuristic method to reconstruct the history of sequences subject to recombination, J. Molecular Evoluation 36 (1993) 396-405; Y. Song, J. Hein, Parsimonious reconstruction of sequence evolution and haplotype blocks: finding the minimum number of recombination events, in: Proceedings of 2003 Workshop on Algorithms in Bioinformatics, Berlin, Germany, 2003, Lecture Notes in Computer Science, Springer, Berlin; Y. Song, J. Hein, On the minimum number of recombination events in the evolutionary history of DNA sequences, J. Math. Biol. 48 (2003) 160-186; L. Wang, K. Zhang, L. Zhang, Perfect phylogenetic networks with recombination, J. Comput. Biol. 8 (2001) 69-78; S.R. Myers, R.C. Griffiths, Bounds on the minimum number of recombination events in a sample history, Genetics 163 (2003) 375-394; V. Bafna, V. Bansal, Improved recombination lower bounds for haplotype data, in: Proceedings of RECOMB, 2005; Y. Song, Y. Wu, D. Gusfield, Efficient computation of close lower and upper bounds on the minimum number of needed recombinations in the evolution of biological sequences, Bioinformatics 21 (2005) i413-i422. Bioinformatics (Suppl. 1), Proceedings of ISMB, 2005, D. Gusfield, S. Eddhu, C. Langley, Optimal, efficient reconstruction of phylogenetic networks with constrained recombination, J. Bioinform. Comput. Biol. 2(1) (2004) 173-213; D. Gusfield, Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination, J. Comput. Systems Sci. 70 (2005) 381-398] is to find a phylogenetic network that derives an input set of sequences, minimizing the number of recombinations used. No efficient, general algorithm is known for this problem. Several papers consider the problem of computing a lower bound on the number of recombinations needed. In this paper we establish a new, efficiently computed lower bound. This result is useful in methods to estimate the number of needed recombinations, and also to prove the optimality of algorithms for constructing phylogenetic networks under certain conditions [D. Gusfield, S. Eddhu, C. Langley, Optimal, efficient reconstruction of phylogenetic networks with constrained recombination, J. Bioinform. Comput. Biol. 2(1) (2004) 173-213; D. Gusfield, Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination, J. Comput. Systems Sci. 70 (2005) 381-398; D. Gusfield, Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained recombination, Technical Report, Department of Computer Science, University of California, Davis, CA, 2004]. The lower bound is based on a structural, combinatorial insight, using only the site conflicts and incompatibilities, and hence it is fundamental and applicable to many biological phenomena other than recombination, for example, when gene conversions or recurrent or back mutations or cross-species hybridizations cause the phylogenetic history to deviate from a tree structure. In addition to establishing the bound, we examine its use in more complex lower bound methods, and compare the bounds obtained to those obtained by other established lower bound methods. © 2006 Elsevier B.V. All rights reserved." @Article{GHE2007,       AUTHOR = {Gusfield, Dan and Hickerson, Dean and Eddhu, Satish},       TITLE = {An efficiently computed lower bound on the number of recombinations in phylogenetic networks: Theory and empirical study},       YEAR = {2007},       JOURNAL = {DAM},       VOLUME = {155},       NUMBER = {6-7},       PAGES = {806-830},       URL = {http://dx.doi.org/10.1016/j.dam.2005.05.044},       NOTE = {http://wwwcsif.cs.ucdavis.edu/~gusfield/cclowerbound.pdf},       ANNOTE = {BIBUPDATE : 20070914} } 42 Stefan Grünewald, Katharina Huber and Qiong Wu. Two novel closure rules for constructing phylogenetic super-networks. In BMB, Vol. 70(7):1906-1924, 2008. Keywords: abstract network, from splits, from unrooted trees, phylogenetic network, phylogeny, Program MY CLOSURE, reconstruction, supernetwork. Note: http://arxiv.org/abs/0709.0283, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/huber/.         Toggle abstract "A contemporary and fundamental problem faced by many evolutionary biologists is how to puzzle together a collection P of partial trees (leaf-labeled trees whose leaves are bijectively labeled by species or, more generally, taxa, each supported by, e.g., a gene) into an overall parental structure that displays all trees in P. This already difficult problem is complicated by the fact that the trees in P regularly support conflicting phylogenetic relationships and are not on the same but only overlapping taxa sets. A desirable requirement on the sought after parental structure, therefore, is that it can accommodate the observed conflicts. Phylogenetic networks are a popular tool capable of doing precisely this. However, not much is known about how to construct such networks from partial trees, a notable exception being the Z-closure super-network approach, which is based on the Z-closure rule, and the Q-imputation approach. Although attractive approaches, they both suffer from the fact that the generated networks tend to be multidimensional making it necessary to apply some kind of filter to reduce their complexity. To avoid having to resort to a filter, we follow a different line of attack in this paper and develop closure rules for generating circular phylogenetic networks which have the attractive property that they can be represented in the plane. In particular, we introduce the novel Y-(closure) rule and show that this rule on its own or in combination with one of Meacham's closure rules (which we call the M-rule) has some very desirable theoretical properties. In addition, we present a case study based on Rivera et al. "ring of life" to explore the reconstructive power of the M- and Y-rule and also reanalyze an Arabidopsis thaliana data set. © 2008 Society for Mathematical Biology." @Article{GHW2008,       AUTHOR = {Gr{\~A}�newald, Stefan and Huber, Katharina and Wu, Qiong},       TITLE = {Two novel closure rules for constructing phylogenetic super-networks},       YEAR = {2008},       JOURNAL = {BMB},       VOLUME = {70},       NUMBER = {7},       PAGES = {1906-1924},       URL = {http://dx.doi.org/10.1007/s11538-008-9331-4},       NOTE = {http://arxiv.org/abs/0709.0283, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/huber/},       ANNOTE = {BIBUPDATE : 20071002},       KEYWORDS = {abstract network, from splits, from unrooted trees, phylogenetic network, phylogeny, Program MY CLOSURE, reconstruction, supernetwork} } 43 Stefan Grünewald, Vincent Moulton and Andreas Spillner. Consistency of the QNet algorithm for generating planar split networks from weighted quartets. In DAM, Vol. 157(10):2325-2334, 2009. Keywords: abstract network, consistency, from quartets, phylogenetic network, phylogeny, Program QNet, reconstruction, software. Note: http://dx.doi.org/10.1016/j.dam.2008.06.038.         Toggle abstract "Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that allow the representation of conflicting signals or alternative evolutionary histories in a single diagram. Recently the Quartet-Net or "QNet" method was introduced, a method for computing a special kind of phylogenetic network called a split network from a collection of weighted quartet trees (i.e. phylogenetic trees with 4 leaves). This can be viewed as a quartet analogue of the distance-based Neighbor-Net (NNet) method for constructing outer-labeled planar split networks. In this paper, we prove that QNet is a consistent method, that is, we prove that if QNet is applied to a collection of weighted quartets arising from a circular split weight function, then it will return precisely this function. This key property of QNet not only ensures that it is guaranteed to produce a tree if the input corresponds to a tree, and an outer-labeled planar split network if the input corresponds to such a network, but also provides the main guiding principle for the design of the method. © 2008 Elsevier B.V. All rights reserved." @Article{GMS2009,       AUTHOR = {Gr{\~A}�newald, Stefan and Moulton, Vincent and Spillner, Andreas},       TITLE = {Consistency of the QNet algorithm for generating planar split networks from weighted quartets},       YEAR = {2009},       JOURNAL = {DAM},       VOLUME = {157},       NUMBER = {10},       PAGES = {2325-2334},       URL = {http://dx.doi.org/10.1016/j.dam.2008.06.038},       NOTE = {http://dx.doi.org/10.1016/j.dam.2008.06.038},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, consistency, from quartets, phylogenetic network, phylogeny, Program QNet, reconstruction, software} } 44 Arndt von Haeseler and Gary A. Churchill. Network models for sequence evolution. In JME, Vol. 37(1):77-85, 1993. Keywords: explicit network, likelihood, phylogenetic network, phylogeny, reconstruction, statistical model. Note: http://dx.doi.org/10.1007/BF00170465.         @Article{HaeselerChurchill1993,       AUTHOR = {von Haeseler, Arndt and Churchill, Gary A.},       TITLE = {Network models for sequence evolution},       YEAR = {1993},       JOURNAL = {JME},       VOLUME = {37},       NUMBER = {1},       PAGES = {77-85},       URL = {http://dx.doi.org/10.1007/BF00170465},       NOTE = {http://dx.doi.org/10.1007/BF00170465},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {explicit network, likelihood, phylogenetic network, phylogeny, reconstruction, statistical model} } 45 Barbara R. Holland, Glenn Conner, Katharina Huber and Vincent Moulton. Imputing Supertrees and Supernetworks from Quartets. In Systematic Biology, Vol. 56(1):57-67, 2007. Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program Quartet, reconstruction, split network, supernetwork. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.99.3215.         Toggle abstract "Inferring species phylogenies is an important part of understanding molecular evolution. Even so, it is well known that an accurate phylogenetic tree reconstruction for a single gene does not always necessarily correspond to the species phylogeny. One commonly accepted strategy to cope with this problem is to sequence many genes; the way in which to analyze the resulting collection of genes is somewhat more contentious. Supermatrix and supertree methods can be used, although these can suppress conflicts arising from true differences in the gene trees caused by processes such as lineage sorting, horizontal gene transfer, or gene duplication and loss. In 2004, Huson et al. (IEEE/ACM Trans. Comput. Biol. Bioinformatics 1:151-158) presented the Z-closure method that can circumvent this problem by generating a supernetwork as opposed to a supertree. Here we present an alternative way for generating supernetworks called Q-imputation. In particular, we describe a method that uses quartet information to add missing taxa into gene trees. The resulting trees are subsequently used to generate consensus networks, networks that generalize strict and majority-rule consensus trees. Through simulations and application to real data sets, we compare Q-imputation to the matrix representation with parsimony (MRP) supertree method and Z-closure, and demonstrate that it provides a useful complementary tool. Copyright © Society of Systematic Biologists." @Article{HCHM2007,       AUTHOR = {Holland, Barbara R. and Conner, Glenn and Huber, Katharina and Moulton, Vincent},       TITLE = {Imputing Supertrees and Supernetworks from Quartets},       YEAR = {2007},       JOURNAL = {Systematic Biology},       VOLUME = {56},       NUMBER = {1},       PAGES = {57-67},       URL = {http://dx.doi.org/10.1080/10635150601167013},       NOTE = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.99.3215},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {abstract network, from unrooted trees, phylogenetic network, phylogeny, Program Quartet, reconstruction, split network, supernetwork} } 46 Daniel H. Huson, Tobias Dezulian, Tobias Kloepper and Mike Steel. Phylogenetic Super-Networks from Partial Trees. In TCBB, Vol. 1(4):151-158, 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 super-network from such data and provides an efficient algorithm for doing so, called the Z-closure 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 plug-in for the program SplitsTree4. © 2004 IEEE." @Article{HDKS2004,       AUTHOR = {Huson, Daniel H. and Dezulian, Tobias and Kloepper, Tobias and Steel, Mike},       TITLE = {Phylogenetic Super-Networks from Partial Trees},       YEAR = {2004},       JOURNAL = {TCBB},       VOLUME = {1},       NUMBER = {4},       PAGES = {151-158},       URL = {http://dx.doi.org/10.1109/TCBB.2004.44},       NOTE = {http://hdl.handle.net/10092/3177},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, supernetwork} } 47 Barbara R. Holland, Frédéric Delsuc and Vincent Moulton. Visualizing Conflicting Evolutionary Hypotheses in Large Collections of Trees: Using Consensus Networks to Study the Origins of Placentals and Hexapods. In Systematic Biology, Vol. 54(1):66-76, 2005. Keywords: consensus. Note: http://hal-sde.archives-ouvertes.fr/halsde-00193050/fr/.         Toggle abstract "Many phylogenetic methods produce large collections of trees as opposed to a single tree, which allows the exploration of support for various evolutionary hypotheses. However, to be useful, the information contained in large collections of trees should be summarized; frequently this is achieved by constructing a consensus tree. Consensus trees display only those signals that are present in a large proportion of the trees. However, by their very nature consensus trees require that any conflicts between the trees are necessarily disregarded. We present a method that extends the notion of consensus trees to allow the visualization of conflicting hypotheses in a consensus network. We demonstrate the utility of this method in highlighting differences amongst maximum likelihood bootstrap values and Bayesian posterior probabilities in the placental mammal phylogeny, and also in comparing the phylogenetic signal contained in amino acid versus nucleotide characters for hexapod monophyly. Copyright © Society of Systematic Biologists." @Article{HDM2005,       AUTHOR = {Holland, Barbara R. and Delsuc, Fr{\~A}�d{\~A}�ric and Moulton, Vincent},       TITLE = {Visualizing Conflicting Evolutionary Hypotheses in Large Collections of Trees: Using Consensus Networks to Study the Origins of Placentals and Hexapods},       YEAR = {2005},       JOURNAL = {Systematic Biology},       VOLUME = {54},       NUMBER = {1},       PAGES = {66-76},       URL = {http://dx.doi.org/10.1080/10635150590906055},       NOTE = {http://hal-sde.archives-ouvertes.fr/halsde-00193050/fr/},       ANNOTE = {BIBUPDATE : 20070920},       KEYWORDS = {consensus} } 48 Jotun Hein. Reconstructing evolution of sequences subject to recombination using parsimony. In MBIO, Vol. 98(2):185-200, 1990. Note: http://dx.doi.org/10.1016/0025-5564(90)90123-G.         Toggle abstract "The parsimony principle states that a history of a set of sequences that minimizes the amount of evolution is a good approximation to the real evolutionary history of the sequences. This principle is applied to the reconstruction of the evolution of homologous sequences where recombinations or horizontal transfer can occur. First it is demonstrated that the appropriate structure to represent the evolution of sequences with recombinations is a family of trees each describing the evolution of a segment of the sequence. Two trees for neighboring segments will differ by exactly the transfer of a subtree within the whole tree. This leads to a metric between trees based on the smallest number of such operations needed to convert one tree into the other. An algorithm is presented that calculates this metric. This metric is used to formulate a dynamic programming algorithm that finds the most parsimonious history that fits a given set of sequences. The algorithm is potentially very practical, since many groups of sequences defy analysis by methods that ignore recombinations. These methods give ambiguous or contradictory results because the sequence history cannot be described by one phylogeny, but only a family of phylogenies that each describe the history of a segment of the sequences. The generalization of the algorithm to reconstruct gene conversions and the possibility for heuristic versions of the algorithm for larger data sets are discussed. © 1990." @Article{Hein1990,       AUTHOR = {Hein, Jotun},       TITLE = {Reconstructing evolution of sequences subject to recombination using parsimony},       YEAR = {1990},       JOURNAL = {MBIO},       VOLUME = {98},       NUMBER = {2},       PAGES = {185-200},       URL = {http://dx.doi.org/10.1016/0025-5564(90)90123-G},       NOTE = {http://dx.doi.org/10.1016/0025-5564(90)90123-G},       ANNOTE = {CITE : } } 49 Jotun Hein. A heuristic method to reconstruct the history of sequences subject to recombination. In JME, Vol. 36(4):396-405, 1993. Keywords: explicit network, from sequences, heuristic, parsimony, phylogenetic network, phylogeny, Program RecPars, recombination, recombination detection, software. Note: http://dx.doi.org/10.1007/BF00182187.         @Article{Hein1993,       AUTHOR = {Hein, Jotun},       TITLE = {A heuristic method to reconstruct the history of sequences subject to recombination},       YEAR = {1993},       JOURNAL = {JME},       VOLUME = {36},       NUMBER = {4},       PAGES = {396-405},       URL = {http://dx.doi.org/10.1007/BF00182187},       NOTE = {http://dx.doi.org/10.1007/BF00182187},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, from sequences, heuristic, parsimony, phylogenetic network, phylogeny, Program RecPars, recombination, recombination detection, software} } 50 Ying-Jun He, Trinh N. D. Huynh, Jesper Jansson and Wing-Kin Sung. Inferring Phylogenetic Relationships Avoiding Forbidden Rooted Triplets. In JBCB, Vol. 4(1):59-74, 2006. Note: http://www.df.lth.se/~jj/Publications/forb_triplets7_JBCB2006.pdf.         Toggle abstract "To construct a phylogenetic tree or phylogenetic network for describing the evolutionary history of a set of species is a well-studied problem in computational biology. One previously proposed method to infer a phylogenetic tree/network for a large set of species is by merging a collection of known smaller phylogenetic trees on overlapping sets of species so that no (or as little as possible) branching information is lost. However, little work has been done so far on inferring a phylogenetic tree/network from a specified set of trees when in addition, certain evolutionary relationships among the species are known to be highly unlikely. In this paper, we consider the problem of constructing a phylogenetic tree/network which is consistent with all of the rooted triplets in a given set C and none of the rooted triplets in another given set F. Although NP-hard in the general case, we provide some efficient exact and approximation algorithms for a number of biologically meaningful variants of the problem. © Imperial College Press." @Article{HHJS2006,       AUTHOR = {He, Ying-Jun and Huynh, Trinh N. D. and Jansson, Jesper and Sung, Wing-Kin},       TITLE = {Inferring Phylogenetic Relationships Avoiding Forbidden Rooted Triplets},       YEAR = {2006},       JOURNAL = {JBCB},       VOLUME = {4},       NUMBER = {1},       PAGES = {59-74},       URL = {http://dx.doi.org/10.1142/S0219720006001709},       NOTE = {http://www.df.lth.se/~jj/Publications/forb_triplets7_JBCB2006.pdf},       ANNOTE = {CITE : } } 51 Barbara R. Holland, Katharina Huber, Vincent Moulton and Peter J. Lockhart. Using consensus networks to visualize contradictory evidence for species phylogeny. In MBE, Vol. 21(7):1459-1461, 2004. Keywords: consensus, from trees, phylogenetic network, phylogeny, split, visualization. Note: http://dx.doi.org/10.1093/molbev/msh145.         Toggle abstract Building species phylogenies from genome data requires the evaluation of phylogenetic evidence from independent gene loci. We propose an approach to do this using consensus networks. We compare gene trees for eight yeast genomes and show that consensus networks have potential for helping to visualize contradictory evidence for species phylogenies. @Article{HHML2004,       AUTHOR = {Holland, Barbara R. and Huber, Katharina and Moulton, Vincent and Lockhart, Peter J.},       TITLE = {Using consensus networks to visualize contradictory evidence for species phylogeny},       YEAR = {2004},       JOURNAL = {MBE},       VOLUME = {21},       NUMBER = {7},       PAGES = {1459-1461},       URL = {http://dx.doi.org/10.1093/molbev/msh145},       NOTE = {http://dx.doi.org/10.1093/molbev/msh145},       KEYWORDS = {consensus, from trees, phylogenetic network, phylogeny, split, visualization} } 52 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):159-161, 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 Lento-plots and median networks. The package is highly interactive and available for PCs. @Article{HLPM2002,       AUTHOR = {Huber, Katharina and Langton, Michael and Penny, David and Moulton, Vincent and Hendy, Mike},       TITLE = {Spectronet: A package for computing spectra and median networks},       YEAR = {2004},       JOURNAL = {ABIO},       VOLUME = {1},       NUMBER = {3},       PAGES = {159-161},       NOTE = {http://citeseer.ist.psu.edu/631776.html},       ANNOTE = {CITE : },       KEYWORDS = {from splits, median network, phylogenetic network, phylogeny, Program Spectronet, software, split, visualization} } 53 Katharina Huber, Vincent Moulton, Peter J. Lockhart and Andreas W. M. Dress. Pruned Median Networks: A Technique for Reducing the Complexity of Median Networks. In MPE, Vol. 19(2):302-310, 2001. Keywords: abstract network, median network, phylogenetic network, phylogeny, split. Note: http://dx.doi.org/10.1006/mpev.2001.0935.         Toggle abstract "Observations from molecular marker studies on recently diverged species indicate that substitution patterns in DNA sequences can often be complex and poorly described by tree-like bifurcating evolutionary models. These observations might result from processes of species diversification and/or processes of sequence evolution that are not tree-like. In these cases, bifurcating tree representations provide poor visualization of phylogenetic signals in sequence data. In this paper, we use median networks to study DNA sequence substitution patterns in plant nuclear and chloroplast markers. We describe how to prune median networks to obtain so called pruned median networks. These simpler networks may help to provide a useful framework for investigating the phylogenetic complexity of recently diverged taxa with hybrid origins. © 2001 Academic Press." @Article{HMPD2001,       AUTHOR = {Huber, Katharina and Moulton, Vincent and Lockhart, Peter J. and Dress, Andreas W. M.},       TITLE = {Pruned Median Networks: A Technique for Reducing the Complexity of Median Networks},       YEAR = {2001},       JOURNAL = {MPE},       VOLUME = {19},       NUMBER = {2},       PAGES = {302-310},       URL = {http://dx.doi.org/10.1006/mpev.2001.0935},       NOTE = {http://dx.doi.org/10.1006/mpev.2001.0935},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, median network, phylogenetic network, phylogeny, split} } 54 Katharina Huber, Vincent Moulton and Charles Semple. Replacing cliques by stars in quasi-median graphs. In DAM, Vol. 143(1-3), 2004. Note: http://dx.doi.org/10.1016/j.dam.2004.03.002.         Toggle abstract "For a multi-set Σ of splits (bipartitions) of a finite set X, we introduce the multi-split 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 multi-split 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." @Article{HMS2004,       AUTHOR = {Huber, Katharina and Moulton, Vincent and Semple, Charles},       TITLE = {Replacing cliques by stars in quasi-median graphs},       YEAR = {2004},       JOURNAL = {DAM},       VOLUME = {143},       NUMBER = {1-3},       URL = {http://dx.doi.org/10.1016/j.dam.2004.03.002},       NOTE = {http://dx.doi.org/10.1016/j.dam.2004.03.002},       ANNOTE = {CITE : } } 55 Katharina Huber, Bengt Oxelman, Martin Lott and Vincent Moulton. Reconstructing the Evolutionary History of Polyploids from Multilabeled Trees. In MBE, Vol. 23(9):1784-1791, 2007. Keywords: duplication, explicit network, from multilabeled tree, from trees, phylogenetic network, phylogeny, Program PADRE, reconstruction, software. Note: http://mbe.oxfordjournals.org/cgi/content/full/23/9/1784.         Toggle abstract "In recent studies, phylogenetic networks have been derived from so-called multilabeled trees in order to understand the origins of certain polyploids. Although the trees used in these studies were constructed using sophisticated techniques in phylogenetic analysis, the presented networks were inferred using ad hoc arguments that cannot be easily extended to larger, more complicated examples. In this paper, we present a general method for constructing such networks, which takes as input a multilabeled phylogenetic tree and outputs a phylogenetic network with certain desirable properties. To illustrate the applicability of our method, we discuss its use in reconstructing the evolutionary history of plant allopolyploids. We conclude with a discussion concerning possible future directions. The network construction method has been implemented and is freely available for use from http://www.uea.ac.uk/ ∼a043878/padre.html. © The Author 2006. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved." @Article{HOLM2006,       AUTHOR = {Huber, Katharina and Oxelman, Bengt and Lott, Martin and Moulton, Vincent},       TITLE = {Reconstructing the Evolutionary History of Polyploids from Multilabeled Trees},       YEAR = {2007},       JOURNAL = {MBE},       VOLUME = {23},       NUMBER = {9},       PAGES = {1784-1791},       URL = {http://dx.doi.org/10.1093/molbev/msl045},       NOTE = {http://mbe.oxfordjournals.org/cgi/content/full/23/9/1784},       ANNOTE = {BIBUPDATE : 20071002},       KEYWORDS = {duplication, explicit network, from multilabeled tree, from trees, phylogenetic network, phylogeny, Program PADRE, reconstruction, software} } 56 Vincent Moulton and Katharina Huber. Phylogenetic networks from multi-labelled trees. In JOMB, Vol. 52(5):613-632, 2006. Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction. Note: http://www.uea.ac.uk/~a043878/jmb.pdf.         Toggle abstract "It is now quite well accepted that the evolutionary past of certain species is better represented by phylogenetic networks as opposed to trees. For example, polyploids are typically thought to have resulted through hybridization and duplication, processes that are probably not best represented as bifurcating speciation events. Based on the knowledge of a multi-labelled tree relating collection of polyploids, we present a canonical construction of a phylogenetic network that exhibits the tree. In addition, we prove that the resulting network is in some well-defined sense a minimal network having this property. © Springer-Verlag 2006." @Article{HuberMoulton2006,       AUTHOR = {Moulton, Vincent and Huber, Katharina},       TITLE = {Phylogenetic networks from multi-labelled trees},       YEAR = {2006},       JOURNAL = {JOMB},       VOLUME = {52},       NUMBER = {5},       PAGES = {613-632},       URL = {http://dx.doi.org/10.1007/s00285-005-0365-z},       NOTE = {http://www.uea.ac.uk/~a043878/jmb.pdf},       ANNOTE = {BIBUPDATE : 20070924},       KEYWORDS = {duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction} } 57 Richard R. Hudson. Properties of the neutral allele model with intragenic recombination. In TPP, Vol. 23:183-201, 1983. Keywords: coalescent. Note: http://dx.doi.org/10.1016/0040-5809(83)90013-8, see also http://www.brics.dk/~compbio/coalescent/hudson_animator.html.         Toggle abstract "An infinite-site neutral allele model with crossing-over possible at any of an infinite number of sites is studied. A formula for the variance of the number of segregating sites in a sample of gametes is obtained. An approximate expression for the expected homozygosity is also derived. Simulation results are presented to indicate the accuracy of the approximations. The results concerning the number of segregating sites and the expected homozygosity indicate that a two-locus model and the infinite-site model behave similarly for 4Nu ≤ 2 and r ≤ 5u, where N is the population size, u is the neutral mutation rate, and r is the recombination rate. Simulations of a two-locus model and a four-locus model were also carried out to determine the effect of intragenic recombination on the homozygosity test ofWatterson (Genetics 85, 789-814; 88, 405-417) and on the number of unique alleles in a sample. The results indicate that for 4Nu ≤ 2 and r ≤ 10u, the effect of recombination is quite small. © 1983." @Article{Hudson1983,       AUTHOR = {Hudson, Richard R.},       TITLE = {Properties of the neutral allele model with intragenic recombination},       YEAR = {1983},       JOURNAL = {TPP},       VOLUME = {23},       PAGES = {183-201},       URL = {http://dx.doi.org/10.1016/0040-5809(83)90013-8},       NOTE = {http://dx.doi.org/10.1016/0040-5809(83)90013-8, see also http://www.brics.dk/~compbio/coalescent/hudson_animator.html},       ANNOTE = {CITE : },       KEYWORDS = {coalescent} } 58 Richard R. Hudson and Norman L. Kaplan. Statistical Properties of the Number of Recombination Events in the History of a Sample of DNA Sequences. In GEN, Vol. 111:147-164, 1985. Note: http://www.genetics.org/cgi/content/abstract/111/1/147.         @Article{HudsonKaplan1985,       AUTHOR = {Hudson, Richard R. and Kaplan, Norman L.},       TITLE = {Statistical Properties of the Number of Recombination Events in the History of a Sample of DNA Sequences},       YEAR = {1985},       JOURNAL = {GEN},       VOLUME = {111},       PAGES = {147-164},       URL = {http://www.ncbi.nlm.nih.gov/pubmed/4029609},       NOTE = {http://www.genetics.org/cgi/content/abstract/111/1/147},       ANNOTE = {CITE : } } 59 Daniel H. Huson. SplitsTree: analyzing and visualizing evolutionary data. In BIO, Vol. 14(1):68-73, 1998. Keywords: abstract network, phylogenetic network, phylogeny, Program SplitsTree, software, split network. Note: http://bioweb.pasteur.fr/docs/doc-gensoft/splitstree/splitstree.ps.         @Article{Huson1998,       AUTHOR = {Huson, Daniel H.},       TITLE = {SplitsTree: analyzing and visualizing evolutionary data},       YEAR = {1998},       JOURNAL = {BIO},       VOLUME = {14},       NUMBER = {1},       PAGES = {68-73},       URL = {http://dx.doi.org/10.1093/bioinformatics/14.1.68},       NOTE = {http://bioweb.pasteur.fr/docs/doc-gensoft/splitstree/splitstree.ps},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, phylogenetic network, phylogeny, Program SplitsTree, software, split network} } 60 Zhi-Zhong Chen and Lusheng Wang. HybridNET: a tool for constructing hybridization networks. In BIO, Vol. 26(22):2912-2913, 2010. Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, Program HybridNET, software. Note: http://rnc.r.dendai.ac.jp/~chen/papers/note2.pdf.         Toggle abstract "Motivations: When reticulation events occur, the evolutionary history of a set of existing species can be represented by a hybridization network instead of an evolutionary tree. When studying the evolutionary history of a set of existing species, one can obtain a phylogenetic tree of the set of species with high confidence by looking at a segment of sequences or a set of genes. When looking at another segment of sequences, a different phylogenetic tree can be obtained with high confidence too. This indicates that reticulation events may occur. Thus, we have the following problem: given two rooted phylogenetic trees on a set of species that correctly represent the tree-like evolution of different parts of their genomes, what is the hybridization network with the smallest number of reticulation events to explain the evolution of the set of species under consideration? Results: We develop a program, named HybridNet, for constructing a hybridization network with the minimum number of reticulate vertices from two input trees. We first implement the O(3dn)-time algorithm by Whidden et al. for computing a maximum (acyclic) agreement forest. Our program can output all the maximum (acyclic) agreement forests. We then augment the program so that it can construct an optimal hybridization network for each given maximum acyclic agreement forest. To our knowledge, this is the first time that optimal hybridization networks can be rapidly constructed. © The Author 2010. Published by Oxford University Press. All rights reserved." @Article{ChenWang2010,       AUTHOR = {Chen, Zhi-Zhong and Wang, Lusheng},       TITLE = {HybridNET: a tool for constructing hybridization networks},       YEAR = {2010},       JOURNAL = {BIO},       VOLUME = {26},       NUMBER = {22},       PAGES = {2912-2913},       URL = {http://dx.doi.org/10.1093/bioinformatics/btq548},       NOTE = {http://rnc.r.dendai.ac.jp/~chen/papers/note2.pdf},       KEYWORDS = {agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, Program HybridNET, software} } 61 Daniel H. Huson and David Bryant. Application of Phylogenetic Networks in Evolutionary Studies. In MBE, Vol. 23(2):254-267, 2006. Keywords: abstract network, phylogenetic network, phylogeny, Program SplitsTree, software, survey. Note: http://dx.doi.org/10.1093/molbev/msj030, software available from www.splitstree.org.         Toggle abstract "The evolutionary history of a set of taxa is usually represented by a phylogenetic tree, and this model has greatly facilitated the discussion and testing of hypotheses. However, it is well known that more complex evolutionary scenarios are poorly described by such models. Further, even when evolution proceeds in a tree-like manner, analysis of the data may not be best served by using methods that enforce a tree structure but rather by a richer visualization of the data to evaluate its properties, at least as an essential first step. Thus, phylogenetic networks should be employed when reticulate events such as hybridization, horizontal gene transfer, recombination, or gene duplication and loss are believed to be involved, and, even in the absence of such events, phylogenetic networks have a useful role to play. This article reviews the terminology used for phylogenetic networks and covers both split networks and reticulate networks, how they are defined, and how they can be interpreted. Additionally, the article outlines the beginnings of a comprehensive statistical framework for applying split network methods. We show how split networks can represent confidence sets of trees and introduce a conservative statistical test for whether the conflicting signal in a network is treelike. Finally, this article describes a new program, SplitsTree4, an interactive and comprehensive tool for inferring different types of phylogenetic networks from sequences, distances, and trees. © The Author 2005. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved." @Article{HusonBryant2006,       AUTHOR = {Huson, Daniel H. and Bryant, David},       TITLE = {Application of Phylogenetic Networks in Evolutionary Studies},       YEAR = {2006},       JOURNAL = {MBE},       VOLUME = {23},       NUMBER = {2},       PAGES = {254-267},       URL = {http://dx.doi.org/10.1093/molbev/msj030},       NOTE = {http://dx.doi.org/10.1093/molbev/msj030, software available from www.splitstree.org},       ANNOTE = {http://dx.doi.org/10.1093/molbev/msj030},       KEYWORDS = {abstract network, phylogenetic network, phylogeny, Program SplitsTree, software, survey} } 62 Jesper Jansson and Wing-Kin Sung. Inferring a level-1 phylogenetic network from a dense set of rooted triplets. In TCS, Vol. 363(1):60-68, 2006. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/ipnrt8_TCS2006.pdf.         Toggle abstract "We consider the following problem: Given a set T of rooted triplets with leaf set L, determine whether there exists a phylogenetic network consistent with T, and if so, construct one. We show that if no restrictions are placed on the hybrid nodes in the solution, the problem is trivially solved in polynomial time by a simple sorting network-based construction. For the more interesting (and biologically more motivated) case where the solution is required to be a level-1 phylogenetic network, we present an algorithm solving the problem in O (| T |2) time when T is dense, i.e., when T contains at least one rooted triplet for each cardinality three subset of L. We also give an O (| T |5 / 3)-time algorithm for finding the set of all phylogenetic networks having a single hybrid node attached to exactly one leaf (and having no other hybrid nodes) that are consistent with a given dense set of rooted triplets. © 2006 Elsevier B.V. All rights reserved." @Article{JanssonSung2006,       AUTHOR = {Jansson, Jesper and Sung, Wing-Kin},       TITLE = {Inferring a level-1 phylogenetic network from a dense set of rooted triplets},       YEAR = {2006},       JOURNAL = {TCS},       VOLUME = {363},       NUMBER = {1},       PAGES = {60-68},       URL = {http://dx.doi.org/10.1016/j.tcs.2006.06.022},       NOTE = {http://www.df.lth.se/~jj/Publications/ipnrt8_TCS2006.pdf},       KEYWORDS = {explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction} } 63 Jesper Jansson, Nguyen Bao Nguyen and Wing-Kin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SICOMP, Vol. 35(5):1098-1121, 2006. Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/triplets_to_gn7_SICOMP2006.pdf.         Toggle abstract "This paper considers the problem of determining whether a given set Τ of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input Τ is dense, we solve the problem in O(|Τ|) time, which is optimal since the size of the input is Θ(|Τ|). In comparison, the previously fastest algorithm for this problem runs in O(|Τ|2) time. We also develop an optimal O(|Τ|)-time algorithm for enumerating all simple phylogenetic networks leaf-labeled by L that are consistent with Τ, where L is the set of leaf labels in Τ, which is used by our main algorithm. Next, we prove that the problem becomes NP-hard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set Τ of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883 ·|Τ| of the rooted triplets in Τ. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (> 0.4166) of the rooted triplets in Τ. © 2006 Society for Industrial and Applied Mathematics." @Article{JNS2006,       AUTHOR = {Jansson, Jesper and Nguyen, Nguyen Bao and Sung, Wing-Kin},       TITLE = {Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network},       YEAR = {2006},       JOURNAL = {SICOMP},       VOLUME = {35},       NUMBER = {5},       PAGES = {1098-1121},       URL = {http://dx.doi.org/10.1137/S0097539704446529},       NOTE = {http://www.df.lth.se/~jj/Publications/triplets_to_gn7_SICOMP2006.pdf},       KEYWORDS = {approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction} } 64 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Maximum Likelihood of Phylogenetic Networks. In BIO, Vol. 22(21):2604-2611, 2006. Keywords: explicit network, likelihood, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/NetworksML06.pdf, supplementary material: http://www.cs.rice.edu/~nakhleh/Papers/Supp-ML.pdf.         @Article{JNST2006b,       AUTHOR = {Jin, Guohua and Nakhleh, Luay and Snir, Sagi and Tuller, Tamir},       TITLE = {Maximum Likelihood of Phylogenetic Networks},       YEAR = {2006},       JOURNAL = {BIO},       VOLUME = {22},       NUMBER = {21},       PAGES = {2604-2611},       URL = {http://dx.doi.org/10.1093/bioinformatics/btl452},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/NetworksML06.pdf, supplementary material: http://www.cs.rice.edu/~nakhleh/Papers/Supp-ML.pdf},       ANNOTE = {BIBUPDATE : 20070917},       KEYWORDS = {explicit network, likelihood, phylogenetic network, phylogeny, Program Nepal, reconstruction} } 65 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Inferring Phylogenetic Networks by the Maximum Parsimony Criterion: A Case Study. In MBE, Vol. 24(1):324-337, 2007. Keywords: explicit network, parsimony, phylogenetic network, phylogeny, Program Nepal, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/MBE06.pdf.         @Article{JNST2007b,       AUTHOR = {Jin, Guohua and Nakhleh, Luay and Snir, Sagi and Tuller, Tamir},       TITLE = {Inferring Phylogenetic Networks by the Maximum Parsimony Criterion: A Case Study},       YEAR = {2007},       JOURNAL = {MBE},       VOLUME = {24},       NUMBER = {1},       PAGES = {324-337},       URL = {http://dx.doi.org/10.1093/molbev/msl163},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/MBE06.pdf},       ANNOTE = {BIBUPDATE : 20070917},       KEYWORDS = {explicit network, parsimony, phylogenetic network, phylogeny, Program Nepal, reconstruction} } 66 John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set of sequences. In DAM, Pages 239-260, 1998. Keywords: from sequences, NP complete, polynomial, recombination, reconstruction. Note: http://citeseer.ist.psu.edu/76600.html.         @Article{KececiogluGusfield1998,       AUTHOR = {Kececioglu, John and Gusfield, Dan},       TITLE = {Reconstructing a history of recombinations from a set of sequences},       YEAR = {1998},       JOURNAL = {DAM},       PAGES = {239-260},       URL = {http://dx.doi.org/10.1016/S0166-218X(98)00074-2},       NOTE = {http://citeseer.ist.psu.edu/76600.html},       ANNOTE = {BIBUPDATE : 20070917},       KEYWORDS = {from sequences, NP complete, polynomial, recombination, reconstruction} } 67 Victor Kunin, Leon Goldovsky, Nikos Darzentas and Christos A. Ouzounis. The net of life: Reconstructing the microbial phylogenetic network. In GR, Vol. 15:954-959, 2005. Note: http://dx.doi.org/10.1101/gr.3666505.         Toggle abstract "It has previously been suggested that the phylogeny of microbial species might be better described as a network containing vertical and horizontal gene transfer (HGT) events. Yet, all phylogenetic reconstructions so far have presented microbial trees rather than networks. Here, we present a first attempt to reconstruct such an evolutionary network, which we term the "net of life." We use available tree reconstruction methods to infer vertical inheritance, and use an ancestral state inference algorithm to map HGT events on the tree. We also describe a weighting scheme used to estimate the number of genes exchanged between pairs of organisms. We demonstrate that vertical inheritance constitutes the bulk of gene transfer on the tree of life. We term the bulk of horizontal gene flow between tree nodes as "vines," and demonstrate that multiple but mostly tiny vines interconnect the tree. Our results strongly suggest that the HGT network is a scale-free graph, a finding with important implications for genome evolution. We propose that genes might propagate extremely rapidly across microbial species through the HGT network, using certain organisms as hubs. ©2005 by Cold Spring Harbor Laboratory Press." @Article{KGDO2005,       AUTHOR = {Kunin, Victor and Goldovsky, Leon and Darzentas, Nikos and Ouzounis, Christos A.},       TITLE = {The net of life: Reconstructing the microbial phylogenetic network},       YEAR = {2005},       JOURNAL = {GR},       VOLUME = {15},       PAGES = {954-959},       URL = {http://dx.doi.org/10.1101/gr.3666505},       NOTE = {http://dx.doi.org/10.1101/gr.3666505},       ANNOTE = {CITE : } } 68 Martyn Kennedy, Barbara R. Holland, Russel D. Gray and Hamish G. Spencer. Untangling Long Branches: Identifying Conflicting Phylogenetic Signals Using Spectral Analysis, Neighbor-Net, and Consensus Networks. In Systematic Biology, Vol. 54(4):620-633, 2005. Keywords: abstract network, consensus, NeighborNet, phylogenetic network, phylogeny. Note: http://awcmee.massey.ac.nz/people/bholland/pdf/Kennedy_etal_2005.pdf.         @Article{KHGS2005,       AUTHOR = {Kennedy, Martyn and Holland, Barbara R. and Gray, Russel D. and Spencer, Hamish G.},       TITLE = {Untangling Long Branches: Identifying Conflicting Phylogenetic Signals Using Spectral Analysis, Neighbor-Net, and Consensus Networks},       YEAR = {2005},       JOURNAL = {Systematic Biology},       VOLUME = {54},       NUMBER = {4},       PAGES = {620-633},       URL = {http://dx.doi.org/10.1080/106351591007462},       NOTE = {http://awcmee.massey.ac.nz/people/bholland/pdf/Kennedy_etal_2005.pdf},       ANNOTE = {BIBUPDATE : 20070920},       KEYWORDS = {abstract network, consensus, NeighborNet, phylogenetic network, phylogeny} } 69 Iyad A. Kanj, Luay Nakhleh and Ge Xia. The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms. In ALG, Vol. 51(2):99-128, 2008. Keywords: perfect, phylogenetic network, phylogeny. Note: http://www.cs.rice.edu/~nakhleh/Papers/algorithmica.pdf.         @Article{KNX2008,       AUTHOR = {Kanj, Iyad A. and Nakhleh, Luay and Xia, Ge},       TITLE = {The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms},       YEAR = {2008},       JOURNAL = {ALG},       VOLUME = {51},       NUMBER = {2},       PAGES = {99-128},       URL = {http://dx.doi.org/10.1007/s00453-007-9046-1},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/algorithmica.pdf},       ANNOTE = {CITE : },       KEYWORDS = {perfect, phylogenetic network, phylogeny} } 70 François-Joseph Lapointe. How to account for reticulation events in phylogenetic analysis: A review of distance-based methods. In Journal of Classification, Vol. 17:175-184, 2000. Keywords: abstract network, evaluation, from distances, phylogenetic network, Program Pyramids, Program SplitsTree, Program T REX, pyramid, reconstruction, reticulogram, split network, survey, weak hierarchy. Note: http://dx.doi.org/10.1007/s003570000016.         @Article{Lapointe2000,       AUTHOR = {Lapointe, Fran{\~A}�ois-Joseph},       TITLE = {How to account for reticulation events in phylogenetic analysis: A review of distance-based methods},       YEAR = {2000},       JOURNAL = {Journal of Classification},       VOLUME = {17},       PAGES = {175-184},       URL = {http://dx.doi.org/10.1007/s003570000016},       NOTE = {http://dx.doi.org/10.1007/s003570000016},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, evaluation, from distances, phylogenetic network, Program Pyramids, Program SplitsTree, Program T REX, pyramid, reconstruction, reticulogram, split network, survey, weak hierarchy} } 71 Pierre Legendre. Reticulate evolution: From bacteria to philosophers. In JCLA, Vol. 17:153-157, 2000. Note: http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf.         @Article{Legendre2000a,       AUTHOR = {Legendre, Pierre},       TITLE = {Reticulate evolution: From bacteria to philosophers},       YEAR = {2000},       JOURNAL = {JCLA},       VOLUME = {17},       PAGES = {153-157},       URL = {http://dx.doi.org/10.1007/s003570000013},       NOTE = {http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf},       ANNOTE = {BIBUPDATE : 20070918} } 72 Pierre Legendre. Biological Applications of Reticulate Analysis. In JCLA, Vol. 17:191-195, 2000. Note: http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf.         @Article{Legendre2000b,       AUTHOR = {Legendre, Pierre},       TITLE = {Biological Applications of Reticulate Analysis},       YEAR = {2000},       JOURNAL = {JCLA},       VOLUME = {17},       PAGES = {191-195},       URL = {http://dx.doi.org/10.1007/s003570000018},       NOTE = {http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf},       ANNOTE = {BIBUPDATE : 20070918} } 73 Pierre Legendre and Vladimir Makarenkov. Reconstruction of biogeographic and evolutionary networks using reticulograms. In Systematic Biology, Vol. 51(2):199-216, 2002. Keywords: phylogenetic network, phylogeny, reconstruction, reticulogram. Note: http://www.labunix.uqam.ca/~makarenv/makarenv/Article_SB.pdf.         @Article{LegendreMakarenkov2002,       AUTHOR = {Legendre, Pierre and Makarenkov, Vladimir},       TITLE = {Reconstruction of biogeographic and evolutionary networks using reticulograms},       YEAR = {2002},       JOURNAL = {Systematic Biology},       VOLUME = {51},       NUMBER = {2},       PAGES = {199-216},       URL = {http://dx.doi.org/10.1080/10635150252899725},       NOTE = {http://www.labunix.uqam.ca/~makarenv/makarenv/Article_SB.pdf},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {phylogenetic network, phylogeny, reconstruction, reticulogram} } 74 C. Randal Linder and Loren H. Rieseberg. Reconstructing patterns of reticulate evolution in plants. In American Journal of Botany, Vol. 91(10):1700-1708, 2004. Keywords: distance between networks, hybridization, phylogenetic network, phylogeny, reconstruction, survey, tripartition distance. Note: http://www.amjbot.org/cgi/reprint/91/10/1700.pdf.         @Article{LinderRieseberg2004,       AUTHOR = {Linder, C. Randal and Rieseberg, Loren H.},       TITLE = {Reconstructing patterns of reticulate evolution in plants},       YEAR = {2004},       JOURNAL = {American Journal of Botany},       VOLUME = {91},       NUMBER = {10},       PAGES = {1700-1708},       URL = {http://dx.doi.org/10.3732/ajb.91.10.1700},       NOTE = {http://www.amjbot.org/cgi/reprint/91/10/1700.pdf},       ANNOTE = {BIBUPDATE : 20070904},       KEYWORDS = {distance between networks, hybridization, phylogenetic network, phylogeny, reconstruction, survey, tripartition distance} } 75 Vladimir Makarenkov. T-REX: reconstructing and visualizing phylogenetic trees and reticulation networks. In BIO, Vol. 17(7):664-668, 2001. Keywords: phylogenetic network, phylogeny, Program T REX, reconstruction, reticulogram, software, visualization. Note: http://www.labunix.uqam.ca/~makarenv/makarenv/Article_BIO.pdf.         @Article{Makarenkov2001,       AUTHOR = {Makarenkov, Vladimir},       TITLE = {T-REX: reconstructing and visualizing phylogenetic trees and reticulation networks},       YEAR = {2001},       JOURNAL = {BIO},       VOLUME = {17},       NUMBER = {7},       PAGES = {664-668},       URL = {http://dx.doi.org/10.1093/bioinformatics/17.7.664},       NOTE = {http://www.labunix.uqam.ca/~makarenv/makarenv/Article_BIO.pdf},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {phylogenetic network, phylogeny, Program T REX, reconstruction, reticulogram, software, visualization} } 76 Vladimir Makarenkov and Pierre Legendre. From a phylogenetic tree to a reticulated network. In JCB, Vol. 11(1):195-212, 2004. Keywords: abstract network, from distances, phylogenetic network, phylogeny, Program T REX, reticulogram. Note: http://www.labunix.uqam.ca/~makarenv/makarenv/article_JCB2004.pdf.         @Article{MakarenkovLegendre2004,       AUTHOR = {Makarenkov, Vladimir and Legendre, Pierre},       TITLE = {From a phylogenetic tree to a reticulated network},       YEAR = {2004},       JOURNAL = {JCB},       VOLUME = {11},       NUMBER = {1},       PAGES = {195-212},       URL = {http://dx.doi.org/10.1089/106652704773416966},       NOTE = {http://www.labunix.uqam.ca/~makarenv/makarenv/article_JCB2004.pdf},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {abstract network, from distances, phylogenetic network, phylogeny, Program T REX, reticulogram} } 77 Vladimir Makarenkov, Pierre Legendre and Yves Desdevises. Modeling phylogenetic relationships using reticulated networks. In Zoologica Scripta, Vol. 33(1):89-96, 2004. Note: http://www.labunix.uqam.ca/~makarenv/articles/ZoologicaScripta.pdf.         @Article{MLD2004,       AUTHOR = {Makarenkov, Vladimir and Legendre, Pierre and Desdevises, Yves},       TITLE = {Modeling phylogenetic relationships using reticulated networks},       YEAR = {2004},       JOURNAL = {Zoologica Scripta},       VOLUME = {33},       NUMBER = {1},       PAGES = {89-96},       URL = {http://dx.doi.org/10.1111/j.1463-6409.2004.00141.x},       NOTE = {http://www.labunix.uqam.ca/~makarenv/articles/ZoologicaScripta.pdf},       ANNOTE = {BIBUPDATE : 20070918} } 78 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):13-23, 2004. Keywords: distance between networks, evaluation, phylogenetic network, phylogeny, time consistent network, tripartition distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb04.pdf.         @Article{MNWRTPST2004,       AUTHOR = {Moret, Bernard M. E. and Nakhleh, Luay and Warnow, Tandy and Linder, C. Randal and Tholse, Anna and Padolina, Anneke and Sun, Jerry and Timme, Ruth},       TITLE = {Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy},       YEAR = {2004},       JOURNAL = {TCBB},       VOLUME = {1},       NUMBER = {1},       PAGES = {13-23},       URL = {http://dx.doi.org/10.1109/tcbb.2004.10},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/tcbb04.pdf},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {distance between networks, evaluation, phylogenetic network, phylogeny, time consistent network, tripartition distance} } 79 Monique M. Morin and Bernard M. E. Moret. NetGen: generating phylogenetic networks with diploid hybrids. In BIO, Vol. 22(15):1921-1923, 2006. Keywords: generation, hybridization, Program NetGen, software. Note: http://dx.doi.org/10.1093/bioinformatics/btl191.         Toggle abstract "Summary: NetGen is an event-driven simulator that creates phylogenetic networks by extending the birth-death model to include diploid hybridizations. DNA sequences are evolved in conjunction with the topology, enabling hybridization decisions to be based on contemporary evolutionary distances. NetGen supports variable rate lineages, root sequence specification, outgroup generation and many other options. This note describes the NetGen application and proposes an extension of the Newick format to accommodate phylogenetic networks. © 2006 Oxford University Press." @Article{MorinMoret2006,       AUTHOR = {Morin, Monique M. and Moret, Bernard M. E.},       TITLE = {NetGen: generating phylogenetic networks with diploid hybrids},       YEAR = {2006},       JOURNAL = {BIO},       VOLUME = {22},       NUMBER = {15},       PAGES = {1921-1923},       URL = {http://dx.doi.org/10.1093/bioinformatics/btl191},       NOTE = {http://dx.doi.org/10.1093/bioinformatics/btl191},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {generation, hybridization, Program NetGen, software} } 80 David A. Morrison. Networks in phylogenetic analysis: new tools for population biology. In IJP, Vol. 35:567-582, 2005. Keywords: median network, NeighborNet, phylogenetic network, phylogeny, population genetics, Program Network, Program Spectronet, Program SplitsTree, Program T REX, Program TCS, reconstruction, reticulogram, split decomposition, survey. Note: http://hem.fyristorg.com/acacia/papers/networks.pdf.         @Article{Morrison2005,       AUTHOR = {Morrison, David A.},       TITLE = {Networks in phylogenetic analysis: new tools for population biology},       YEAR = {2005},       JOURNAL = {IJP},       VOLUME = {35},       PAGES = {567-582},       URL = {http://dx.doi.org/10.1016/j.ijpara.2005.02.007},       NOTE = {http://hem.fyristorg.com/acacia/papers/networks.pdf},       ANNOTE = {CITE : },       KEYWORDS = {median network, NeighborNet, phylogenetic network, phylogeny, population genetics, Program Network, Program Spectronet, Program SplitsTree, Program T REX, Program TCS, reconstruction, reticulogram, split decomposition, survey} } 81 Simon R. Myers and Robert C. Griffiths. Bounds on the Minimum Number of Recombination Events in a Sample History. In GEN, Vol. 163:375-394, 2003. Keywords: Program RecMin. Note: http://www.genetics.org/cgi/content/abstract/163/1/375.         @Article{MyersGriffiths2003,       AUTHOR = {Myers, Simon R. and Griffiths, Robert C.},       TITLE = {Bounds on the Minimum Number of Recombination Events in a Sample History},       YEAR = {2003},       JOURNAL = {GEN},       VOLUME = {163},       PAGES = {375-394},       NOTE = {http://www.genetics.org/cgi/content/abstract/163/1/375},       ANNOTE = {CITE : },       KEYWORDS = {Program RecMin} } 82 Cam Thach Nguyen, Nguyen Bao Nguyen and Wing-Kin Sung. Fast Algorithms for computing the Tripartition-based Distance between Phylogenetic Networks. In JCO, Vol. 13(3), 2007. Keywords: distance between networks, phylogenetic network, phylogeny, tripartition distance. Note: http://dx.doi.org/10.1007/s10878-006-9025-5.         Toggle abstract "Consider two phylogenetic networks N and N′ of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by N and N′. This distance is proposed by Moret et al. (2004) and is a generalization of Robinson-Foulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an O(min {kn log n, n log n + hn} -time algorithm to compute this distance, where h is the number of hybrid nodes in N and N′ while k is the maximum number of hybrid nodes among all biconnected components in N and N′. Note that k ≪ h ≪ n in a phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which are an important, biological meaningful special case of phylogenetic network. We give an O(n)-time algorithm for comparing two galled-trees. We also give an O(n + kh)-time algorithm for comparing a galled-tree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively. © Springer Science+Business Media, LLC 2007." @Article{NNS2007,       AUTHOR = {Nguyen, Cam Thach and Nguyen, Nguyen Bao and Sung, Wing-Kin},       TITLE = {Fast Algorithms for computing the Tripartition-based Distance between Phylogenetic Networks},       YEAR = {2007},       JOURNAL = {JCO},       VOLUME = {13},       NUMBER = {3},       URL = {http://dx.doi.org/10.1007/s10878-006-9025-5},       NOTE = {http://dx.doi.org/10.1007/s10878-006-9025-5},       ANNOTE = {BIBUPDATE : 20071118},       KEYWORDS = {distance between networks, phylogenetic network, phylogeny, tripartition distance} } 83 Cam Thach Nguyen, Nguyen Bao Nguyen, Wing-Kin Sung and Louxin Zhang. Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem. In TCBB, Vol. 4(3):394-402, 2007. Keywords: explicit network, from sequences, labeling, NP complete, parsimony, phylogenetic network, phylogeny. Note: http://www.cs.washington.edu/homes/ncthach/Papers/TCBB2007.pdf.         @Article{NNSZ2007,       AUTHOR = {Nguyen, Cam Thach and Nguyen, Nguyen Bao and Sung, Wing-Kin and Zhang, Louxin},       TITLE = {Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem},       YEAR = {2007},       JOURNAL = {TCBB},       VOLUME = {4},       NUMBER = {3},       PAGES = {394-402},       URL = {http://dx.doi.org/10.1109/tcbb.2007.1018},       NOTE = {http://www.cs.washington.edu/homes/ncthach/Papers/TCBB2007.pdf},       ANNOTE = {BIBUPDATE : 20071118},       KEYWORDS = {explicit network, from sequences, labeling, NP complete, parsimony, phylogenetic network, phylogeny} } 84 Luay Nakhleh, Don Ringe and Tandy Warnow. Perfect Phylogenetic Networks: A New Methodology for Reconstructing the Evolutionary History of Natural Languages. In Language, Journal of the Linguistic Society of America, Vol. 81(2):382-420, 2002. Keywords: perfect, phylogenetic network, phylogeny. Note: http://www.cs.rice.edu/~nakhleh/Papers/81.2nakhleh.pdf.         @Article{NRW2005b,       AUTHOR = {Nakhleh, Luay and Ringe, Don and Warnow, Tandy},       TITLE = {Perfect Phylogenetic Networks: A New Methodology for Reconstructing the Evolutionary History of Natural Languages},       YEAR = {2002},       JOURNAL = {Language, Journal of the Linguistic Society of America},       VOLUME = {81},       NUMBER = {2},       PAGES = {382-420},       URL = {http://dx.doi.org/10.1353/lan.2005.0078},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/81.2nakhleh.pdf},       ANNOTE = {CITE : },       KEYWORDS = {perfect, phylogenetic network, phylogeny} } 85 Luay Nakhleh, Tandy Warnow, C. Randal Linder and Katherine St. John. Reconstructing reticulate evolution in species - theory and practice. In JCB, Vol. 12(6):796-811, 2005. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/NWLSjcb.pdf.         @Article{NWLS2005,       AUTHOR = {Nakhleh, Luay and Warnow, Tandy and Linder, C. Randal and St. John, Katherine},       TITLE = {Reconstructing reticulate evolution in species - theory and practice},       YEAR = {2005},       JOURNAL = {JCB},       VOLUME = {12},       NUMBER = {6},       PAGES = {796-811},       URL = {http://dx.doi.org/10.1089/cmb.2005.12.796},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/NWLSjcb.pdf},       ANNOTE = {BIBUPDATE : 20071002},       KEYWORDS = {from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software} } 86 David Posada, Keith A. Crandall and Edward C. Holmes. Recombination in Evolutionary Genomics. In ARG, Vol. 36:75-97, 2002. Keywords: phylogenetic network, phylogeny, recombination, recombination detection, survey. Note: http://dx.doi.org/10.1146/annurev.genet.36.040202.111115.         Toggle abstract "Recombination can be a dominant force in shaping genomes and associated phenotypes. To better understand the impact of recombination on genomic evolution, we need to be able to identify recombination in aligned sequences. We review bioinformatic approaches for detecting recombination and measuring recombination rates. We also examine the impact of recombination on the reconstruction of evolutionary histories and the estimation of population genetic parameters. Finally, we review the role of recombination in the evolutionary history of bacteria, viruses, and human mitochondria. We conclude by highlighting a number of areas for future development of tools to help quantify the role of recombination in genomic evolution." @Article{PCH2002,       AUTHOR = {Posada, David and Crandall, Keith A. and Holmes, Edward C.},       TITLE = {Recombination in Evolutionary Genomics},       YEAR = {2002},       JOURNAL = {ARG},       VOLUME = {36},       PAGES = {75-97},       URL = {http://dx.doi.org/10.1146/annurev.genet.36.040202.111115},       NOTE = {http://dx.doi.org/10.1146/annurev.genet.36.040202.111115},       ANNOTE = {BIBUPDATE : 20070927},       KEYWORDS = {phylogenetic network, phylogeny, recombination, recombination detection, survey} } 87 David Posada and Keith A. Crandall. The effect of recombination on the accuracy of phylogeny estimation. In JME, Pages 396-402, 2002. Note: http://darwin.uvigo.es/download/papers/17.recPhylo02.pdf.         @Article{PosadaCrandall2002,       AUTHOR = {Posada, David and Crandall, Keith A.},       TITLE = {The effect of recombination on the accuracy of phylogeny estimation},       YEAR = {2002},       JOURNAL = {JME},       PAGES = {396-402},       URL = {http://dx.doi.org/10.1007/s00239-001-0034-9},       NOTE = {http://darwin.uvigo.es/download/papers/17.recPhylo02.pdf},       ANNOTE = {BIBUPDATE : 20070919} } 88 David Posada and Keith A. Crandall. Intraspecific gene genealogies: trees grafting into networks. In TEE, Vol. 16(1):37-45, 2001. Keywords: likelihood, median network, netting, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program SplitsTree, Program T REX, Program TCS, pyramid, reticulogram, split decomposition, statistical parsimony, survey. Note: http://darwin.uvigo.es/download/papers/09.networks01.pdf.         @Article{PosadaCrandall2001,       AUTHOR = {Posada, David and Crandall, Keith A.},       TITLE = {Intraspecific gene genealogies: trees grafting into networks},       YEAR = {2001},       JOURNAL = {TEE},       VOLUME = {16},       NUMBER = {1},       PAGES = {37-45},       URL = {http://dx.doi.org/10.1016/s0169-5347(00)02026-7},       NOTE = {http://darwin.uvigo.es/download/papers/09.networks01.pdf},       ANNOTE = {BIBUPDATE : 20070917},       KEYWORDS = {likelihood, median network, netting, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program SplitsTree, Program T REX, Program TCS, pyramid, reticulogram, split decomposition, statistical parsimony, survey} } 89 F. James Rohlf. Phylogenetic models and reticulations. In JCLA, Vol. 17:185-189, 2000. Note: http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf.         @Article{Rohlf2000,       AUTHOR = {Rohlf, F. James},       TITLE = {Phylogenetic models and reticulations},       YEAR = {2000},       JOURNAL = {JCLA},       VOLUME = {17},       PAGES = {185-189},       URL = {http://dx.doi.org/10.1007/s003570000017},       NOTE = {http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf},       ANNOTE = {BIBUPDATE : 20070918} } 90 Derek Ruths and Luay Nakhleh. Recombination and phylogeny: effects and detection. In IJBRA, Pages 202-212, 2005. Note: http://www.cs.rice.edu/~nakhleh/Papers/IJBRA05.pdf.         @Article{RuthsNakhleh2005,       AUTHOR = {Ruths, Derek and Nakhleh, Luay},       TITLE = {Recombination and phylogeny: effects and detection},       YEAR = {2005},       JOURNAL = {IJBRA},       PAGES = {202-212},       URL = {http://dx.doi.org/10.1504/ijbra.2005.007578},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/IJBRA05.pdf},       ANNOTE = {BIBUPDATE : 20070918} } 91 Mikkel H. Schierup and Jotun Hein. Consequences of recombination on traditional phylogenetic analysis. In GEN, Vol. 156:879-891, 2000. Note: http://www.birc.dk/Publications/Articles/Schierup_2000b.pdf.         @Article{SchierupHein2000a,       AUTHOR = {Schierup, Mikkel H. and Hein, Jotun},       TITLE = {Consequences of recombination on traditional phylogenetic analysis},       YEAR = {2000},       JOURNAL = {GEN},       VOLUME = {156},       PAGES = {879-891},       NOTE = {http://www.birc.dk/Publications/Articles/Schierup_2000b.pdf},       ANNOTE = {BIBUPDATE : 20070917} } 92 Mikkel H. Schierup and Jotun Hein. Recombination and the molecular clock. In MBE, Vol. 17(10):1578-1579, 2000. Note: http://www.birc.dk/Publications/Articles/Schierup_2000c.pdf.         @Article{SchierupHein2000b,       AUTHOR = {Schierup, Mikkel H. and Hein, Jotun},       TITLE = {Recombination and the molecular clock},       YEAR = {2000},       JOURNAL = {MBE},       VOLUME = {17},       NUMBER = {10},       PAGES = {1578-1579},       URL = {http://dx.doi.org/10.1093/oxfordjournals.molbev.a026256},       NOTE = {http://www.birc.dk/Publications/Articles/Schierup_2000c.pdf},       ANNOTE = {BIBUPDATE : 20070917} } 93 Charles Semple and Mike Steel. Unicyclic networks: compatibility and enumeration. In TCBB, Vol. 3(1):84-91, 2006. Keywords: counting, explicit network, galled tree, unicyclic network. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/SS06.pdf.         @Article{SempleSteel2006,       AUTHOR = {Semple, Charles and Steel, Mike},       TITLE = {Unicyclic networks: compatibility and enumeration},       YEAR = {2006},       JOURNAL = {TCBB},       VOLUME = {3},       NUMBER = {1},       PAGES = {84-91},       URL = {http://dx.doi.org/10.1109/tcbb.2006.14},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/SS06.pdf},       ANNOTE = {ISSUE : 1},       KEYWORDS = {counting, explicit network, galled tree, unicyclic network} } 94 Peter E. Smouse. Reticulation inside the species boundary. In JCLA, Vol. 17:165-173, 2000. Note: http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf.         @Article{Smouse2000,       AUTHOR = {Smouse, Peter E.},       TITLE = {Reticulation inside the species boundary},       YEAR = {2000},       JOURNAL = {JCLA},       VOLUME = {17},       PAGES = {165-173},       URL = {http://dx.doi.org/10.1007/s003570000015},       NOTE = {http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf},       ANNOTE = {BIBUPDATE : 20070918} } 95 Peter H. A. Sneath. Cladistic Representation of Reticulate Evolution. In Systematic Zoology, Vol. 24(3):165-173, 1975. Keywords: explicit network, from rooted trees, from species tree, hybridization, parsimony, phylogeny. Note: http://dx.doi.org/10.2307/2412721.         @Article{Sneath1975,       AUTHOR = {Sneath, Peter H. A.},       TITLE = {Cladistic Representation of Reticulate Evolution},       YEAR = {1975},       JOURNAL = {Systematic Zoology},       VOLUME = {24},       NUMBER = {3},       PAGES = {165-173},       URL = {http://dx.doi.org/10.2307/2412721},       NOTE = {http://dx.doi.org/10.2307/2412721},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, from rooted trees, from species tree, hybridization, parsimony, phylogeny} } 96 Peter H. A. Sneath. Reticulate Evolution in Bacteria and Other Organisms: How Can We Study It? In JCLA, Vol. 17:360-368, 2000. Note: http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf.         @Article{Sneath2000,       AUTHOR = {Sneath, Peter H. A.},       TITLE = {Reticulate Evolution in Bacteria and Other Organisms: How Can We Study It?},       YEAR = {2000},       JOURNAL = {JCLA},       VOLUME = {17},       PAGES = {360-368},       URL = {http://dx.doi.org/10.1007/s003570000014},       NOTE = {http://www.bio.umontreal.ca/legendre/reprints/Special_Section.pdf},       ANNOTE = {BIBUPDATE : 20070918} } 97 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):160-186, 2004. Keywords: minimum number, recombination. Note: http://dx.doi.org/10.1007/s00285-003-0227-5.         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. © Springer-Verlag 2003." @Article{SongHein2004,       AUTHOR = {Song, Yun S. and Hein, Jotun},       TITLE = {On the Minimum Number of Recombination Events in the Evolutionary History of DNA Sequences},       YEAR = {2004},       JOURNAL = {JOMB},       VOLUME = {48},       NUMBER = {2},       PAGES = {160-186},       URL = {http://dx.doi.org/10.1007/s00285-003-0227-5},       NOTE = {http://dx.doi.org/10.1007/s00285-003-0227-5},       ANNOTE = {CITE : },       KEYWORDS = {minimum number, recombination} } 98 Yun S. Song and Jotun Hein. Constructing Minimal Ancestral Recombination Graphs. In JCB, Vol. 12(2):147-169, 2005. Keywords: ARG, minimum number, recombination. Note: http://www.eecs.berkeley.edu/~yss/Pub/SH-JCB05.pdf.         @Article{SongHein2005,       AUTHOR = {Song, Yun S. and Hein, Jotun},       TITLE = {Constructing Minimal Ancestral Recombination Graphs},       YEAR = {2005},       JOURNAL = {JCB},       VOLUME = {12},       NUMBER = {2},       PAGES = {147-169},       URL = {http://dx.doi.org/10.1089/cmb.2005.12.147},       NOTE = {http://www.eecs.berkeley.edu/~yss/Pub/SH-JCB05.pdf},       ANNOTE = {CITE : },       KEYWORDS = {ARG, minimum number, recombination} } 99 Andreas Spillner, Binh T. Nguyen and Vincent Moulton. Computing phylogenetic diversity for split systems. In TCBB, Vol. 5(2):235-244, 2008. Keywords: abstract network, diversity, phylogenetic network, phylogeny, split. Note: http://dx.doi.org/10.1109/TCBB.2007.70260, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0906/spillner/.         Toggle abstract "In conservation biology it is a central problem to measure, predict, and preserve biodiversity as species face extinction. In 1992 Faith proposed measuring the diversity of a collection of species in terms of their relationships on a phylogenetic tree, and to use this information to identify collections of species with high diversity. Here we are interested in some variants of the resulting optimization problem that arise when considering species whose evolution is better represented by a network rather than a tree. More specifically, we consider the problem of computing phylogenetic diversity relative to a split system on a collection of species of size $n$. We show that for general split systems this problem is NP-hard. In addition we provide some efficient algorithms for some special classes of split systems, in particular presenting an optimal $O(n)$ time algorithm for phylogenetic trees and an $O(nlog n + n k)$ time algorithm for choosing an optimal subset of size $k$ relative to a circular split system. © 2006 IEEE." @Article{SNM2008,       AUTHOR = {Spillner, Andreas and Nguyen, Binh T. and Moulton, Vincent},       TITLE = {Computing phylogenetic diversity for split systems},       YEAR = {2008},       JOURNAL = {TCBB},       VOLUME = {5},       NUMBER = {2},       PAGES = {235-244},       URL = {http://dx.doi.org/10.1109/TCBB.2007.70260},       NOTE = {http://dx.doi.org/10.1109/TCBB.2007.70260, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0906/spillner/},       ANNOTE = {BIBUPDATE : 20070924},       KEYWORDS = {abstract network, diversity, phylogenetic network, phylogeny, split} } 100 Korbinian Strimmer and Vincent Moulton. Likelihood Analysis of Phylogenetic Networks Using Directed Graphical Models. In MBE, Vol. 17(6):875-881, 2000. Keywords: bayesian, likelihood, median network, split network, statistical model. Note: http://mbe.oxfordjournals.org/cgi/content/abstract/17/6/875.         @Article{StrimmerMoulton2000,       AUTHOR = {Strimmer, Korbinian and Moulton, Vincent},       TITLE = {Likelihood Analysis of Phylogenetic Networks Using Directed Graphical Models},       YEAR = {2000},       JOURNAL = {MBE},       VOLUME = {17},       NUMBER = {6},       PAGES = {875-881},       URL = {http://dx.doi.org/10.1093/oxfordjournals.molbev.a026367},       NOTE = {http://mbe.oxfordjournals.org/cgi/content/abstract/17/6/875},       ANNOTE = {BIBUPDATE : 20070917},       KEYWORDS = {bayesian, likelihood, median network, split network, statistical model} } 101 Korbinian Strimmer, Carsten Wiuf and Vincent Moulton. Recombination Analysis Using Directed Graphical Models. In MBE, Vol. 18(1):97-99, 2001. Keywords: recombination, statistical model. Note: http://mbe.oxfordjournals.org/cgi/content/full/18/1/97.         @Article{SWM2001,       AUTHOR = {Strimmer, Korbinian and Wiuf, Carsten and Moulton, Vincent},       TITLE = {Recombination Analysis Using Directed Graphical Models},       YEAR = {2001},       JOURNAL = {MBE},       VOLUME = {18},       NUMBER = {1},       PAGES = {97-99},       URL = {http://dx.doi.org/10.1093/oxfordjournals.molbev.a003725},       NOTE = {http://mbe.oxfordjournals.org/cgi/content/full/18/1/97},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {recombination, statistical model} } 102 Alan R. Templeton, Keith A. Crandall and Charles F. Sing. A Cladistic Analysis of Phenotypic Associations With Haplotypes Inferred From Restriction Endonuclease Mapping and DNA Sequence Data. III. Cladogram Estimation. In GEN, Vol. 132:619-633, 2000. Keywords: from sequences, parsimony, phylogenetic network, phylogeny, Program TCS, recombination, reconstruction, statistical parsimony. Note: http://www.genetics.org/cgi/content/abstract/132/2/619.         @Article{TCS1992,       AUTHOR = {Templeton, Alan R. and Crandall, Keith A. and Sing, Charles F.},       TITLE = {A Cladistic Analysis of Phenotypic Associations With Haplotypes Inferred From Restriction Endonuclease Mapping and DNA Sequence Data. III. Cladogram Estimation},       YEAR = {2000},       JOURNAL = {GEN},       VOLUME = {132},       PAGES = {619-633},       NOTE = {http://www.genetics.org/cgi/content/abstract/132/2/619},       ANNOTE = {CITE : },       KEYWORDS = {from sequences, parsimony, phylogenetic network, phylogeny, Program TCS, recombination, reconstruction, statistical parsimony} } 103 Richard C. Winkworth, David Bryant, Peter J. Lockhart, David Havell and Vincent Moulton. Biogeographic Interpretation of Splits Graphs: Least Squares Optimization of Branch Lengths. In Systematic Biology, Vol. 54(1):56-65, 2005. Keywords: abstract network, from distances, from network, phylogenetic network, phylogeny, reconstruction, split, split network. Note: http://www.math.auckland.ac.nz/~bryant/Papers/05Biogeographic.pdf.         @Article{WBLHM2005,       AUTHOR = {Winkworth, Richard C. and Bryant, David and Lockhart, Peter J. and Havell, David and Moulton, Vincent},       TITLE = {Biogeographic Interpretation of Splits Graphs: Least Squares Optimization of Branch Lengths},       YEAR = {2005},       JOURNAL = {Systematic Biology},       VOLUME = {54},       NUMBER = {1},       PAGES = {56-65},       URL = {http://dx.doi.org/10.1080/10635150590906046},       NOTE = {http://www.math.auckland.ac.nz/~bryant/Papers/05Biogeographic.pdf},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, from distances, from network, phylogenetic network, phylogeny, reconstruction, split, split network} } 104 Stephen J. Willson. Unique solvability of certain hybrid networks from their distances. In ACOM, Vol. 10(1):165-178, 2006. Keywords: from distances, from network, labeling, phylogenetic network, phylogeny. Note: http://www.public.iastate.edu/~swillson/Solvability.pdf.         @Article{Willson2006a,       AUTHOR = {Willson, Stephen J.},       TITLE = {Unique solvability of certain hybrid networks from their distances},       YEAR = {2006},       JOURNAL = {ACOM},       VOLUME = {10},       NUMBER = {1},       PAGES = {165-178},       URL = {http://dx.doi.org/10.1007/s00026-006-0280-z},       NOTE = {http://www.public.iastate.edu/~swillson/Solvability.pdf},       ANNOTE = {BIBUPDATE : 20070924},       KEYWORDS = {from distances, from network, labeling, phylogenetic network, phylogeny} } 105 Stephen J. Willson. Unique Reconstruction of Tree-Like Phylogenetic Networks from Distances Between Leaves. In BMB, Vol. 68:919-944, 2006. Keywords: explicit network, from distances, identifiability, mrca network, phylogenetic network, phylogeny, reconstruction. Note: http://www.public.iastate.edu/~swillson/BMB05-07.rev8.pdf.         @Article{Willson2006b,       AUTHOR = {Willson, Stephen J.},       TITLE = {Unique Reconstruction of Tree-Like Phylogenetic Networks from Distances Between Leaves},       YEAR = {2006},       JOURNAL = {BMB},       VOLUME = {68},       PAGES = {919-944},       URL = {http://dx.doi.org/10.1007/s11538-005-9044-x},       NOTE = {http://www.public.iastate.edu/~swillson/BMB05-07.rev8.pdf},       ANNOTE = {BIBUPDATE : 20070924},       KEYWORDS = {explicit network, from distances, identifiability, mrca network, phylogenetic network, phylogeny, reconstruction} } 106 Stephen J. Willson. Unique determination of some homoplasies at hybridization events. In BMB, Vol. 69(5):1709-1725, 2007. Keywords: explicit network, from network, hybridization, labeling, normal network, phylogenetic network, tree-child network. Note: http://www.public.iastate.edu/~swillson/unique.det.pdf.         @Article{Willson2007a,       AUTHOR = {Willson, Stephen J.},       TITLE = {Unique determination of some homoplasies at hybridization events},       YEAR = {2007},       JOURNAL = {BMB},       VOLUME = {69},       NUMBER = {5},       PAGES = {1709-1725},       URL = {http://dx.doi.org/10.1007/s11538-006-9187-4},       NOTE = {http://www.public.iastate.edu/~swillson/unique.det.pdf},       ANNOTE = {BIBUPDATE : 20071216},       KEYWORDS = {explicit network, from network, hybridization, labeling, normal network, phylogenetic network, tree-child network} } 107 Stephen J. Willson. Reconstruction of Some Hybrid Phylogenetic Networks with Homoplasies from Distances. In BMB, Vol. 69(8):2561-2590, 2007. Keywords: explicit network, from distances, normal network, phylogenetic network, phylogeny, reconstruction. Note: http://www.public.iastate.edu/~swillson/BMB06-97.willson.pdf.         @Article{Willson2007c,       AUTHOR = {Willson, Stephen J.},       TITLE = {Reconstruction of Some Hybrid Phylogenetic Networks with Homoplasies from Distances},       YEAR = {2007},       JOURNAL = {BMB},       VOLUME = {69},       NUMBER = {8},       PAGES = {2561-2590},       URL = {http://dx.doi.org/10.1007/s11538-007-9232-y},       NOTE = {http://www.public.iastate.edu/~swillson/BMB06-97.willson.pdf},       ANNOTE = {BIBUPDATE : 20071216},       KEYWORDS = {explicit network, from distances, normal network, phylogenetic network, phylogeny, reconstruction} } 108 Daniel H. Huson and Celine Scornavacca. A survey of combinatorial methods for phylogenetic networks. In Genome Biology and Evolution, Vol. 3:23-35, 2011. Keywords: phylogenetic network, survey. Note: http://dx.doi.org/10.1093/gbe/evq077.         Toggle abstract "The evolutionary history of a set of species is usually described by a rooted phylogenetic tree. Although it is generally undisputed that bifurcating speciation events and descent with modifications are major forces of evolution, there is a growing belief that reticulate events also have a role to play. Phylogenetic networks provide an alternative to phylogenetic trees and may be more suitable for data sets where evolution involves significant amounts of reticulate events, such as hybridization, horizontal gene transfer, or recombination. In this article, we give an introduction to the topic of phylogenetic networks, very briefly describing the fundamental concepts and summarizing some of the most important combinatorial methods that are available for their computation. © 2010 The Author(s)." @Article{HusonScornavacca2011,       AUTHOR = {Huson, Daniel H. and Scornavacca, Celine},       TITLE = {A survey of combinatorial methods for phylogenetic networks},       YEAR = {2011},       JOURNAL = {Genome Biology and Evolution},       VOLUME = {3},       PAGES = {23-35},       URL = {http://dx.doi.org/10.1093/gbe/evq077},       NOTE = {http://dx.doi.org/10.1093/gbe/evq077},       KEYWORDS = {phylogenetic network, survey} } 109 Yufeng Wu and Dan Gusfield. Efficient Computation of Minimum Recombination with Genotypes (not Haplotypes) In JBCB, Vol. 5(2(a)):181-200, 2007. Note: http://dx.doi.org/10.1142/S0219720007002631.         @Article{WuGusfield2007a,       AUTHOR = {Wu, Yufeng and Gusfield, Dan},       TITLE = {Efficient Computation of Minimum Recombination with Genotypes (not Haplotypes)},       YEAR = {2007},       JOURNAL = {JBCB},       VOLUME = {5},       NUMBER = {2(a)},       PAGES = {181-200},       URL = {http://dx.doi.org/10.1142/S0219720007002631},       NOTE = {http://dx.doi.org/10.1142/S0219720007002631},       ANNOTE = {CITE : } } 110 Shizhong Xu. Phylogenetic Analysis Under Reticulate Evolution. In MBE, Vol. 17(6):897-907, 2000. Keywords: from distances, phylogenetic network, phylogeny, reconstruction, statistical model. Note: http://mbe.oxfordjournals.org/cgi/content/abstract/17/6/897.         @Article{Xu2000,       AUTHOR = {Xu, Shizhong},       TITLE = {Phylogenetic Analysis Under Reticulate Evolution},       YEAR = {2000},       JOURNAL = {MBE},       VOLUME = {17},       NUMBER = {6},       PAGES = {897-907},       URL = {http://dx.doi.org/10.1093/oxfordjournals.molbev.a026370},       NOTE = {http://mbe.oxfordjournals.org/cgi/content/abstract/17/6/897},       ANNOTE = {BIBUPDATE : 20070918},       KEYWORDS = {from distances, phylogenetic network, phylogeny, reconstruction, statistical model} } 111 David Bryant, Vincent Moulton and Andreas Spillner. Consistency of the Neighbor-Net Algorithm. In AMB, Vol. 2(8), 2007. Keywords: abstract network, consistency, from distances, NeighborNet. Note: http://dx.doi.org/10.1186/1748-7188-2-8.         Toggle abstract "Background: Neighbor-Net is a novel method for phylogenetic analysis that is currently being widely used in areas such as virology, bacteriology, and plant evolution. Given an input distance matrix, Neighbor-Net produces a phylogenetic network, a generalization of an evolutionary or phylogenetic tree which allows the graphical representation of conflicting phylogenetic signals. Results: In general, any network construction method should not depict more conflict than is found in the data, and, when the data is fitted well by a tree, the method should return a network that is close to this tree. In this paper we provide a formal proof that Neighbor-Net satisfies both of these requirements so that, in particular, Neighbor-Net is statistically consistent on circular distances. © 2007 Bryant et al; licensee BioMed Central Ltd." @Article{BMS2007,       AUTHOR = {Bryant, David and Moulton, Vincent and Spillner, Andreas},       TITLE = {Consistency of the Neighbor-Net Algorithm},       YEAR = {2007},       JOURNAL = {AMB},       VOLUME = {2},       NUMBER = {8},       URL = {http://dx.doi.org/10.1186/1748-7188-2-8},       NOTE = {http://dx.doi.org/10.1186/1748-7188-2-8},       ANNOTE = {BIBUPDATE : 20071117},       KEYWORDS = {abstract network, consistency, from distances, NeighborNet} } 112 Esra Erdem, Vladimir Lifschitz and Don Ringe. Temporal phylogenetic networks and logic programming. In Theory and Practice of Logic Programming, Vol. 6:539-558, 2006. Note: http://arxiv.org/abs/cs/0508129v1.         @Article{ELR2006,       AUTHOR = {Erdem, Esra and Lifschitz, Vladimir and Ringe, Don},       TITLE = {Temporal phylogenetic networks and logic programming},       YEAR = {2006},       JOURNAL = {Theory and Practice of Logic Programming},       VOLUME = {6},       PAGES = {539-558},       URL = {http://dx.doi.org/10.1017/S1471068406002729},       NOTE = {http://arxiv.org/abs/cs/0508129v1},       ANNOTE = {CITE : } } 113 Bhaskar DasGupta, Sergio Ferrarini, Uthra Gopalakrishnan and Nisha Raj Paryani. Inapproximability results for the lateral gene transfer problem. In JCO, Vol. 11(4):387-405, 2006. Keywords: approximation, from rooted trees, from species tree, inapproximability, lateral gene transfer, parsimony, phylogenetic network, phylogeny. Note: http://www.cs.uic.edu/~dasgupta/resume/publ/papers/t-scenario-3-reviewed-3.pdf.         @Article{DFGP2006,       AUTHOR = {DasGupta, Bhaskar and Ferrarini, Sergio and Gopalakrishnan, Uthra and Paryani, Nisha Raj},       TITLE = {Inapproximability results for the lateral gene transfer problem},       YEAR = {2006},       JOURNAL = {JCO},       VOLUME = {11},       NUMBER = {4},       PAGES = {387-405},       URL = {http://dx.doi.org/10.1007/s10878-006-8212-8},       NOTE = {http://www.cs.uic.edu/~dasgupta/resume/publ/papers/t-scenario-3-reviewed-3.pdf},       ANNOTE = {BIBUPDATE : 20071120},       KEYWORDS = {approximation, from rooted trees, from species tree, inapproximability, lateral gene transfer, parsimony, phylogenetic network, phylogeny} } 114 Dave MacLeod, Robert L. Charlebois, W. Ford Doolittle and Eric Bapteste. Deduction of probable events of lateral gene transfer through comparison of phylogenetic trees by recursive consolidation and rearrangement. In BMCEB, Vol. 5(27), 2005. Keywords: explicit network, from rooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program HorizStory, reconstruction, software. Note: http://dx.doi.org/10.1186/1471-2148-5-27.         Toggle abstract "Background: When organismal phylogenies based on sequences of single marker genes are poorly resolved, a logical approach is to add more markers, on the assumption that weak but congruent phylogenetic signal will be reinforced in such multigene trees. Such approaches are valid only when the several markers indeed have identical phylogenies, an issue which many multigene methods (such as the use of concatenated gene sequences or the assembly of supertrees) do not directly address. Indeed, even when the true history is a mixture of vertical descent for some genes and lateral gene transfer (LGT) for others, such methods produce unique topologies. Results: We have developed software that aims to extract evidence for vertical and lateral inheritance from a set of gene trees compared against an arbitrary reference tree. This evidence is then displayed as a synthesis showing support over the tree for vertical inheritance, overlaid with explicit lateral gene transfer (LGT) events inferred to have occurred over the history of the tree. Like splits-tree methods, one can thus identify nodes at which conflict occurs. Additionally one can make reasonable inferences about vertical and lateral signal, assigning putative donors and recipients. Conclusion: A tool such as ours can serve to explore the reticulated dimensionality of molecular evolution, by dissecting vertical and lateral inheritance at high resolution. By this, we mean that individual nodes can be examined not only for congruence, but also for coherence in light of LGT. We assert that our tools will facilitate the comparison of phylogenetic trees, and the interpretation of conflicting data. © 2005 MacLeod et al; licensee BioMed Central Ltd." @Article{MCDB2005,       AUTHOR = {MacLeod, Dave and Charlebois, Robert L. and Doolittle, W. Ford and Bapteste, Eric},       TITLE = {Deduction of probable events of lateral gene transfer through comparison of phylogenetic trees by recursive consolidation and rearrangement},       YEAR = {2005},       JOURNAL = {BMCEB},       VOLUME = {5},       NUMBER = {27},       URL = {http://dx.doi.org/10.1186/1471-2148-5-27},       NOTE = {http://dx.doi.org/10.1186/1471-2148-5-27},       ANNOTE = {BIBUPDATE : 20071120},       KEYWORDS = {explicit network, from rooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program HorizStory, reconstruction, software} } 115 Robert G. Beiko and Nicholas Hamilton. Phylogenetic identification of lateral genetic transfer events. In BMCEB, Vol. 6(15), 2006. Keywords: evaluation, from rooted trees, from unrooted trees, lateral gene transfer, Program EEEP, Program HorizStory, Program LatTrans, reconstruction, software, SPR distance. Note: http://dx.doi.org/10.1186/1471-2148-6-15.         Toggle abstract "Background: Lateral genetic transfer can lead to disagreements among phylogenetic trees comprising sequences from the same set of taxa. Where topological discordance is thought to have arisen through genetic transfer events, tree comparisons can be used to identify the lineages that may have shared genetic information. An 'edit path' of one or more transfer events can be represented with a series of subtree prune and regraft (SPR) operations, but finding the optimal such set of operations is NP-hard for comparisons between rooted trees, and may be so for unrooted trees as well. Results: Efficient Evaluation of Edit Paths (EEEP) is a new tree comparison algorithm that uses evolutionarily reasonable constraints to identify and eliminate many unproductive search avenues, reducing the time required to solve many edit path problems. The performance of EEEP compares favourably to that of other algorithms when applied to strictly bifurcating trees with specified numbers of SPR operations. We also used EEEP to recover edit paths from over 19 000 unrooted, incompletely resolved protein trees containing up to 144 taxa as part of a large phylogenomic study. While inferred protein trees were far more similar to a reference supertree than random trees were to each other, the phylogenetic distance spanned by random versus inferred transfer events was similar, suggesting that real transfer events occur most frequently between closely related organisms, but can span large phylogenetic distances as well. While most of the protein trees examined here were very similar to the reference supertree, requiring zero or one edit operations for reconciliation, some trees implied up to 40 transfer events within a single orthologous set of proteins. Conclusion: Since sequence trees typically have no implied root and may contain unresolved or multifurcating nodes, the strategy implemented in EEEP is the most appropriate for phylogenomic analyses. The high degree of consistency among inferred protein trees shows that vertical inheritance is the dominant pattern of evolution, at least for the set of organisms considered here. However, the edit paths inferred using EEEP suggest an important role for genetic transfer in the evolution of microbial genomes as well. © 2006Beiko and Hamilton; licensee BioMed Central Ltd." @Article{BeikoHamilton2006,       AUTHOR = {Beiko, Robert G. and Hamilton, Nicholas},       TITLE = {Phylogenetic identification of lateral genetic transfer events},       YEAR = {2006},       JOURNAL = {BMCEB},       VOLUME = {6},       NUMBER = {15},       URL = {http://dx.doi.org/10.1186/1471-2148-6-15},       NOTE = {http://dx.doi.org/10.1186/1471-2148-6-15},       ANNOTE = {BIBUPDATE : 20071120},       KEYWORDS = {evaluation, from rooted trees, from unrooted trees, lateral gene transfer, Program EEEP, Program HorizStory, Program LatTrans, reconstruction, software, SPR distance} } 116 Maria S. Poptsova and J. Peter Gogarten. The power of phylogenetic approaches to detect horizontally transferred genes. In BMCEB, Vol. 7(45), 2007. Keywords: evaluation, from rooted trees, lateral gene transfer, Program EEEP. Note: http://dx.doi.org/10.1186/1471-2148-7-45.         Toggle abstract "Background. Horizontal gene transfer plays an important role in evolution because it sometimes allows recipient lineages to adapt to new ecological niches. High genes transfer frequencies were inferred for prokaryotic and early eukaryotic evolution. Does horizontal gene transfer also impact phylogenetic reconstruction of the evolutionary history of genomes and organisms? The answer to this question depends at least in part on the actual gene transfer frequencies and on the ability to weed out transferred genes from further analyses. Are the detected transfers mainly false positives, or are they the tip of an iceberg of many transfer events most of which go undetected by current methods? Results. Phylogenetic detection methods appear to be the method of choice to infer gene transfers, especially for ancient transfers and those followed by orthologous replacement. Here we explore how well some of these methods perform using in silico transfers between the terminal branches of a gamma proteobacterial, genome based phylogeny. For the experiments performed here on average the AU test at a 5% significance level detects 90.3% of the transfers and 91% of the exchanges as significant. Using the Robinson-Foulds distance only 57.7% of the exchanges and 60% of the donations were identified as significant. Analyses using bipartition spectra appeared most successful in our test case. The power of detection was on average 97% using a 70% cut-off and 94.2% with 90% cut-off for identifying conflicting bipartitions, while the rate of false positives was below 4.2% and 2.1% for the two cut-offs, respectively. For all methods the detection rates improved when more intervening branches separated donor and recipient. Conclusion. Rates of detected transfers should not be mistaken for the actual transfer rates; most analyses of gene transfers remain anecdotal. The method and significance level to identify potential gene transfer events represent a trade-off between the frequency of erroneous identification (false positives) and the power to detect actual transfer events. © 2007 Poptsova and Gogarten; licensee BioMed Central Ltd." @Article{PoptsovaGogarten2007,       AUTHOR = {Poptsova, Maria S. and Gogarten, J. Peter},       TITLE = {The power of phylogenetic approaches to detect horizontally transferred genes},       YEAR = {2007},       JOURNAL = {BMCEB},       VOLUME = {7},       NUMBER = {45},       URL = {http://dx.doi.org/10.1186/1471-2148-7-45},       NOTE = {http://dx.doi.org/10.1186/1471-2148-7-45},       ANNOTE = {BIBUPDATE : 20071120},       KEYWORDS = {evaluation, from rooted trees, lateral gene transfer, Program EEEP} } 117 Daniel H. Huson, Daniel C. Richter, Christian Rausch, Tobias Dezulian, Markus Franz and Regula Rupp. Dendroscope: An interactive viewer for large phylogenetic trees. In BMCB, Vol. 8:460, 2007. Keywords: phylogeny, Program Dendroscope, software, visualization. Note: http://dx.doi.org/10.1186/1471-2105-8-460, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0903/huson/, software freely available from http://www.dendroscope.org.         Toggle abstract "Background: Research in evolution requires software for visualizing and editing phylogenetic trees, for increasingly very large datasets, such as arise in expression analysis or metagenomics, for example. It would be desirable to have a program that provides these services in an effcient and user-friendly way, and that can be easily installed and run on all major operating systems. Although a large number of tree visualization tools are freely available, some as a part of more comprehensive analysis packages, all have drawbacks in one or more domains. They either lack some of the standard tree visualization techniques or basic graphics and editing features, or they are restricted to small trees containing only tens of thousands of taxa. Moreover, many programs are diffcult to install or are not available for all common operating systems. Results: We have developed a new program, Dendroscope, for the interactive visualization and navigation of phylogenetic trees. The program provides all standard tree visualizations and is optimized to run interactively on trees containing hundreds of thousands of taxa. The program provides tree editing and graphics export capabilities. To support the inspection of large trees, Dendroscope offers a magnification tool. The software is written in Java 1.4 and installers are provided for Linux/Unix, MacOS X and Windows XP. Conclusion: Dendroscope is a user-friendly program for visualizing and navigating phylogenetic trees, for both small and large datasets. © 2007 Huson et al; licensee BioMed Central Ltd." @Article{HDFRRR2007,       AUTHOR = {Huson, Daniel H. and Richter, Daniel C. and Rausch, Christian and Dezulian, Tobias and Franz, Markus and Rupp, Regula},       TITLE = {Dendroscope: An interactive viewer for large phylogenetic trees},       YEAR = {2007},       JOURNAL = {BMCB},       VOLUME = {8},       PAGES = {460},       URL = {http://dx.doi.org/10.1186/1471-2105-8-460},       NOTE = {http://dx.doi.org/10.1186/1471-2105-8-460, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0903/huson/, software freely available from http://www.dendroscope.org},       ANNOTE = {CITE : },       KEYWORDS = {phylogeny, Program Dendroscope, software, visualization} } 118 Ulrik Brandes and Sabine Cornelsen. Phylogenetic Graph Models Beyond Trees. In DAM, Vol. 157(10):2361-2369, 2009. Keywords: abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf.         Toggle abstract "A graph model for a set S of splits of a set X consists of a graph and a map from X to the vertices of the graph such that the inclusion-minimal cuts of the graph represent S. Phylogenetic trees are graph models in which the graph is a tree. We show that the model can be generalized to a cactus (i.e. a tree of edges and cycles) without losing computational efficiency. A cactus can represent a quadratic rather than linear number of splits in linear space. We show how to decide in linear time in the size of a succinct representation of S whether a set of splits has a cactus model, and if so construct it within the same time bounds. As a byproduct, we show how to construct the subset of all compatible splits and a maximal compatible set of splits in linear time. Note that it is N P-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models. © 2008 Elsevier B.V. All rights reserved." @Article{BrandesCornelsen2009,       AUTHOR = {Brandes, Ulrik and Cornelsen, Sabine},       TITLE = {Phylogenetic Graph Models Beyond Trees},       YEAR = {2009},       JOURNAL = {DAM},       VOLUME = {157},       NUMBER = {10},       PAGES = {2361-2369},       URL = {http://dx.doi.org/10.1016/j.dam.2008.06.031},       NOTE = {http://www.inf.uni-konstanz.de/~cornelse/Papers/bc-pgmbt-07.pdf},       KEYWORDS = {abstract network, cactus graph, from splits, phylogenetic network, phylogeny, polynomial, reconstruction} } 119 Katharina Huber, Elizabeth E. Watson and Mike Hendy. An Algorithm for Constructing Local Regions in a Phylogenetic Network. In MPE, Vol. 19(1):1-8, 2000. Keywords: abstract network, median network, phylogenetic network, phylogeny, reconstruction, split. Note: http://dx.doi.org/10.1006/mpev.2000.0891.         Toggle abstract "The groupings of taxa in a phylogenetic tree cannot represent all the conflicting signals that usually occur among site patterns in aligned homologous genetic sequences. Hence a tree-building program must compromise by reporting a subset of the patterns, using some discriminatory criterion. Thus, in the worst case, out of possibly a large number of equally good trees, only an arbitrarily chosen tree might be reported by the tree-building program as" The Tree." This tree might then be used as a basis for phylogenetic conclusions. One strategy to represent conflicting patterns in the data is to construct a network. The Buneman graph is a theoretically very attractive example of such a network. In particular, a characterization for when this network will be a tree is known. Also the Buneman graph contains each of the most parsimonious trees indicated by the data. In this paper we describe a new method for constructing the Buneman graph that can be used for a generalization of Hadamard conjugation to networks. This new method differs from previous methods by allowing us to focus on local regions of the graph without having to first construct the full graph. The construction is illustrated by an example. © 2001 Academic Press." @Article{HWH2001,       AUTHOR = {Huber, Katharina and Watson, Elizabeth E. and Hendy, Mike},       TITLE = {An Algorithm for Constructing Local Regions in a Phylogenetic Network},       YEAR = {2000},       JOURNAL = {MPE},       VOLUME = {19},       NUMBER = {1},       PAGES = {1-8},       URL = {http://dx.doi.org/10.1006/mpev.2000.0891},       NOTE = {http://dx.doi.org/10.1006/mpev.2000.0891},       ANNOTE = {BIBUPDATE : 20071122},       KEYWORDS = {abstract network, median network, phylogenetic network, phylogeny, reconstruction, split} } 120 Andreas W. M. Dress, Mike Hendy, Katharina Huber and Vincent Moulton. On the number of vertices and edges in the Buneman graph. In ACOM, Vol. 1:329-337, 1997. Keywords: abstract network, median network, phylogenetic network, phylogeny, split. Note: http://dx.doi.org/10.1007/BF02558484.         @Article{DHHM1997,       AUTHOR = {Dress, Andreas W. M. and Hendy, Mike and Huber, Katharina and Moulton, Vincent},       TITLE = {On the number of vertices and edges in the Buneman graph},       YEAR = {1997},       JOURNAL = {ACOM},       VOLUME = {1},       PAGES = {329-337},       URL = {http://dx.doi.org/10.1007/BF02558484},       NOTE = {http://dx.doi.org/10.1007/BF02558484},       ANNOTE = {BIBUPDATE : 20071122},       KEYWORDS = {abstract network, median network, phylogenetic network, phylogeny, split} } 121 Arvind Gupta, Ján Manuch, Xiaohong Zhao and Ladislav Stacho. Characterization of the existence of galled-tree networks. In JBCB, Vol. 4(6):1309-1328, 2006. Keywords: characterization, galled tree. Note: http://www.pims.math.ca/~manuch/papers/characterization_JBCB2006.pdf.         @Article{GMZS2006,       AUTHOR = {Gupta, Arvind and Manuch, J{\~A}�n and Zhao, Xiaohong and Stacho, Ladislav},       TITLE = {Characterization of the existence of galled-tree networks},       YEAR = {2006},       JOURNAL = {JBCB},       VOLUME = {4},       NUMBER = {6},       PAGES = {1309-1328},       URL = {http://dx.doi.org/10.1142/S0219720006002478},       NOTE = {http://www.pims.math.ca/~manuch/papers/characterization_JBCB2006.pdf},       ANNOTE = {CITE : },       KEYWORDS = {characterization, galled tree} } 122 Mohd Abdul Hai Zahid, Ankush Mittal and Ramesh C. Joshi. A pattern recognition-based approach for phylogenetic network construction with constrained recombination. In Pattern Recognition, Vol. 39:2312-2322, 2006. Note: http://www.isical.ac.in/~zahid_t/publications/papers/revision 2.pdf.         @Article{ZMJ2006,       AUTHOR = {Zahid, Mohd Abdul Hai and Mittal, Ankush and Joshi, Ramesh C.},       TITLE = {A pattern recognition-based approach for phylogenetic network construction with constrained recombination},       YEAR = {2006},       JOURNAL = {Pattern Recognition},       VOLUME = {39},       PAGES = {2312-2322},       URL = {http://dx.doi.org/10.1016/j.patcog.2006.06.020},       NOTE = {http://www.isical.ac.in/~zahid_t/publications/papers/revision 2.pdf},       ANNOTE = {BIBUPDATE : 20071126} } 123 Mohd Abdul Hai Zahid, Ankush Mittal and Ramesh C. Joshi. Use of Phylogenetic network and its reconstruction Algorithms. In Bioinformatics India, Vol. 2:47-58, 2004. Keywords: evaluation, from distances, NeighborNet, Program SplitsTree, Program T REX, split decomposition. Note: http://www.isical.ac.in/~zahid_t/publications/papers/1.pdf.         @Article{ZMJ2004,       AUTHOR = {Zahid, Mohd Abdul Hai and Mittal, Ankush and Joshi, Ramesh C.},       TITLE = {Use of Phylogenetic network and its reconstruction Algorithms},       YEAR = {2004},       JOURNAL = {Bioinformatics India},       VOLUME = {2},       PAGES = {47-58},       NOTE = {http://www.isical.ac.in/~zahid_t/publications/papers/1.pdf},       ANNOTE = {ISSUE : 4},       KEYWORDS = {evaluation, from distances, NeighborNet, Program SplitsTree, Program T REX, split decomposition} } 124 Wayne P. Maddison. Gene Trees in Species Trees. In Systematic Biology, Vol. 46(3):523-536, 1997. Keywords: from rooted trees, from species tree, lateral gene transfer, phylogeny, reconstruction, time consistent network. Note: http://dx.doi.org/10.2307/2413694.         @Article{Maddison1997,       AUTHOR = {Maddison, Wayne P.},       TITLE = {Gene Trees in Species Trees},       YEAR = {1997},       JOURNAL = {Systematic Biology},       VOLUME = {46},       NUMBER = {3},       PAGES = {523-536},       URL = {http://dx.doi.org/10.2307/2413694},       NOTE = {http://dx.doi.org/10.2307/2413694},       ANNOTE = {CITE : },       KEYWORDS = {from rooted trees, from species tree, lateral gene transfer, phylogeny, reconstruction, time consistent network} } 125 Dan Gusfield, Vikas Bansal, Vineet Bafna and Yun S. Song. A Decomposition Theory for Phylogenetic Networks and Incompatible Characters. In JCB, Vol. 14(10):1247-1272, 2007. Keywords: explicit network, from sequences, galled tree, phylogenetic network, phylogeny, Program Beagle, Program GalledTree, recombination, reconstruction, software. Note: http://www.eecs.berkeley.edu/~yss/Pub/decomposition.pdf.         @Article{GBBS2007,       AUTHOR = {Gusfield, Dan and Bansal, Vikas and Bafna, Vineet and Song, Yun S.},       TITLE = {A Decomposition Theory for Phylogenetic Networks and Incompatible Characters},       YEAR = {2007},       JOURNAL = {JCB},       VOLUME = {14},       NUMBER = {10},       PAGES = {1247-1272},       URL = {http://dx.doi.org/10.1089/cmb.2006.0137},       NOTE = {http://www.eecs.berkeley.edu/~yss/Pub/decomposition.pdf},       ANNOTE = {BIBUPDATE : 20071206},       KEYWORDS = {explicit network, from sequences, galled tree, phylogenetic network, phylogeny, Program Beagle, Program GalledTree, recombination, reconstruction, software} } 126 Kirill Kryukov and Naruya Saitou. Netview: Application Software for Constructing and Visually Exploring Phylogenetic Networks. In Genome Informatics, Vol. 14:280-281, 2003. Keywords: from sequences, phylogenetic network, phylogeny, Program NetView, visualization. Note: http://www.jsbi.org/journal/GIW03/GIW03SS06.pdf.         @Article{KryukovSaitou2003,       AUTHOR = {Kryukov, Kirill and Saitou, Naruya},       TITLE = {Netview: Application Software for Constructing and Visually Exploring Phylogenetic Networks},       YEAR = {2003},       JOURNAL = {Genome Informatics},       VOLUME = {14},       PAGES = {280-281},       URL = {http://dx.doi.org/10.11234/gi1990.14.280},       NOTE = {http://www.jsbi.org/journal/GIW03/GIW03SS06.pdf},       ANNOTE = {CITE : },       KEYWORDS = {from sequences, phylogenetic network, phylogeny, Program NetView, visualization} } 127 Gabriel Cardona, Francesc Rosselló and Gabriel Valiente. A Perl Package and an Alignment Tool for Phylogenetic Networks. In BMCB, Vol. 9:175, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, Program Bio PhyloNetwork, tree sibling network, tree-child network. Note: http://dx.doi.org/10.1186/1471-2105-9-175.         Toggle abstract "Background: Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of evolutionary events acting at the population level, like recombination between genes, hybridization between lineages, and lateral gene transfer. While most phylogenetics tools implement a wide range of algorithms on phylogenetic trees, there exist only a few applications to work with phylogenetic networks, none of which are open-source libraries, and they do not allow for the comparative analysis of phylogenetic networks by computing distances between them or aligning them. Results: In order to improve this situation, we have developed a Perl package that relies on the BioPerl bundle and implements many algorithms on phylogenetic networks. We have also developed a Java applet that makes use of the aforementioned Perl package and allows the user to make simple experiments with phylogenetic networks without having to develop a program or Perl script by him or herself. Conclusion: The Perl package is available as part of the BioPerl bundle, and can also be downloaded. A web-based application is also available (see availability and requirements). The Perl package includes full documentation of all its features. © 2008 Cardona et al; licensee BioMed Central Ltd." @Article{CRV2008b,       AUTHOR = {Cardona, Gabriel and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {A Perl Package and an Alignment Tool for Phylogenetic Networks},       YEAR = {2008},       JOURNAL = {BMCB},       VOLUME = {9},       PAGES = {175},       URL = {http://dx.doi.org/10.1186/1471-2105-9-175},       NOTE = {http://dx.doi.org/10.1186/1471-2105-9-175},       ANNOTE = {BIBUPDATE : 20080506},       KEYWORDS = {distance between networks, phylogenetic network, phylogeny, Program Bio PhyloNetwork, tree sibling network, tree-child network} } 128 Yun S. Song, Zhihong Ding, Dan Gusfield, Charles Langley and Yufeng Wu. Algorithms to Distinguish the Role of Gene-Conversion from Single-Crossover Recombination in the Derivation of SNP Sequences in Populations. In JCB, Vol. 14(10):1273-1286, 2007. Keywords: ARG, from sequences, phylogenetic network, phylogeny, Program SHRUB, reconstruction. Note: http://dx.doi.org/10.1089/cmb.2007.0096.         Toggle abstract "Meiotic recombination is a fundamental biological event and one of the principal evolutionary forces responsible for shaping genetic variation within species. In addition to its fundamental role, recombination is central to several critical applied problems. The most important example is "association mapping" in populations, which is widely hoped to help find genes that influence genetic diseases (Carlson et al., 2004; Clark, 2003). Hence, a great deal of recent attention has focused on problems of inferring the historical derivation of sequences in populations when both mutations and recombinations have occurred. In the algorithms literature, most of that recent work has been directed to single-crossover recombination. However, gene-conversion is an important, and more common, form of (two-crossover) recombination which has been much less investigated in the algorithms literature. In this paper, we explicitly incorporate gene-conversion into discrete methods to study historical recombination. We are concerned with algorithms for identifying and locating the extent of historical crossing-over and gene-conversion (along with single-nucleotide mutation), and problems of constructing full putative histories of those events. The novel technical issues concern the incorporation of gene-conversion into recently developed discrete methods (Myers and Griffiths, 2003; Song et al., 2005) that compute lower and upper-bound information on the amount of needed recombination without gene-conversion. We first examine the most natural extension of the lower bound methods from Myers and Griffiths (2003), showing that the extension can be computed efficiently, but that this extension can only yield weak lower bounds. We then develop additional ideas that lead to higher lower bounds, and show how to solve, via integer-linear programming, a more biologically realistic version of the lower bound problem. We also show how to compute effective upper bounds on the number of needed single-crossovers and gene-conversions, along with explicit networks showing a putative history of mutations, single-crossovers and gene-conversions. Both lower and upper bound methods can handle data with missing entries, and the upper bound method can be used to infer missing entries with high accuracy. We validate the significance of these methods by showing that they can be effectively used to distinguish simulation-derived sequences generated without gene-conversion from sequences that were generated with gene-conversion. We apply the methods to recently studied sequences of Arabidopsis thaliana, identifying many more regions in the sequences than were previously identified (Plagnol et al., 2006), where gene-conversion may have played a significant role. Demonstration software is available at www.csif.cs.ucdavis.edu/∼gusfield. © 2007 Mary Ann Liebert, Inc." @Article{SDGLW2007,       AUTHOR = {Song, Yun S. and Ding, Zhihong and Gusfield, Dan and Langley, Charles and Wu, Yufeng},       TITLE = {Algorithms to Distinguish the Role of Gene-Conversion from Single-Crossover Recombination in the Derivation of SNP Sequences in Populations},       YEAR = {2007},       JOURNAL = {JCB},       VOLUME = {14},       NUMBER = {10},       PAGES = {1273-1286},       URL = {http://dx.doi.org/10.1089/cmb.2007.0096},       NOTE = {http://dx.doi.org/10.1089/cmb.2007.0096},       ANNOTE = {BIBUPDATE : 20071212},       KEYWORDS = {ARG, from sequences, phylogenetic network, phylogeny, Program SHRUB, reconstruction} } 129 Stephen J. Willson. Reconstruction of certain phylogenetic networks from the genomes at their leaves. In JTB, Vol. 252(2):185-376, 2008. Keywords: labeling, polynomial. Note: http://www.public.iastate.edu/~swillson/ReconstructNormalHomopap6.pdf.         Toggle abstract "A network N is a rooted acyclic digraph. A base-set X for N is a subset of vertices including the root (or outgroup), all leaves, and all vertices of outdegree 1. A simple model of evolution is considered in which all characters are binary and in which back-mutations occur only at hybrid vertices. It is assumed that the genome is known for each member of the base-set X. If the network is known and is assumed to be "normal," then it is proved that the genome of every vertex is uniquely determined and can be explicitly reconstructed. Under additional hypotheses involving time-consistency and separation of the hybrid vertices, the network itself can also be reconstructed from the genomes of all members of X. An explicit polynomial-time procedure is described for performing the reconstruction. © 2008 Elsevier Ltd. All rights reserved." @Article{Willson2008,       AUTHOR = {Willson, Stephen J.},       TITLE = {Reconstruction of certain phylogenetic networks from the genomes at their leaves},       YEAR = {2008},       JOURNAL = {JTB},       VOLUME = {252},       NUMBER = {2},       PAGES = {185-376},       URL = {http://dx.doi.org/10.1016/j.jtbi.2008.02.015},       NOTE = {http://www.public.iastate.edu/~swillson/ReconstructNormalHomopap6.pdf},       ANNOTE = {BIBUPDATE : 20071216},       KEYWORDS = {labeling, polynomial} } 130 Yun S. Song. A Concise Necessary and Sufficient Condition for the Existence of a Galled-Tree. In TCBB, Vol. 3(2):186-191, 2006. Keywords: characterization, from sequences, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.eecs.berkeley.edu/~yss/Pub/nasc4gall.pdf.         @Article{Song2006,       AUTHOR = {Song, Yun S.},       TITLE = {A Concise Necessary and Sufficient Condition for the Existence of a Galled-Tree},       YEAR = {2006},       JOURNAL = {TCBB},       VOLUME = {3},       NUMBER = {2},       PAGES = {186-191},       URL = {http://dx.doi.org/10.1109/TCBB.2006.15},       NOTE = {http://www.eecs.berkeley.edu/~yss/Pub/nasc4gall.pdf},       ANNOTE = {CITE : },       KEYWORDS = {characterization, from sequences, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction} } 131 Patricia Buendia and Giri Narasimhan. Serial NetEvolve: A flexible utility for generating serially-sampled sequences along a tree or recombinant network. In BIO, Vol. 18(22):2313-2314, 2006. Keywords: generation, phylogenetic network, phylogeny, Program Serial NetEvolve, Program Treevolve, recombination, software. Note: http://dx.doi.org/10.1093/bioinformatics/btl387.         Toggle abstract "Summary: Serial NetEvolve is a flexible simulation program that generates DNA sequences evolved along a tree or recombinant network. It offers a user-friendly Windows graphical interface and a Windows or Linux simulator with a diverse selection of parameters to control the evolutionary model. Serial NetEvolve is a modification of the Treevolve program with the following additional features: simulation of serially-sampled data, the choice of either a clock-like or a variable rate model of sequence evolution, sampling from the internal nodes and the output of the randomly generated tree or network in our newly proposed NeTwick format. © 2006 Oxford University Press." @Article{BuendiaNarasimhan2006,       AUTHOR = {Buendia, Patricia and Narasimhan, Giri},       TITLE = {Serial NetEvolve: A flexible utility for generating serially-sampled sequences along a tree or recombinant network},       YEAR = {2006},       JOURNAL = {BIO},       VOLUME = {18},       NUMBER = {22},       PAGES = {2313-2314},       URL = {http://dx.doi.org/10.1093/bioinformatics/btl387},       NOTE = {http://dx.doi.org/10.1093/bioinformatics/btl387},       ANNOTE = {BIBUPDATE : 20071228},       KEYWORDS = {generation, phylogenetic network, phylogeny, Program Serial NetEvolve, Program Treevolve, recombination, software} } 132 Patricia Buendia and Giri Narasimhan. Sliding MinPD: Building evolutionary networks of serial samples via an automated recombination detection approach. In BIO, Vol. 23(22):2993-3000, 2007. Keywords: from sequences, phylogenetic network, phylogeny, Program Sliding MinPD, recombination, recombination detection, serial evolutionary networks, software. Note: http://dx.doi.org/10.1093/bioinformatics/btm413.         Toggle abstract "Motivation: Traditional phylogenetic methods assume tree-like evolutionary models and are likely to perform poorly when provided with sequence data from fast-evolving, recombining viruses. Furthermore, these methods assume that all the sequence data are from contemporaneous taxa, which is not valid for serially-sampled data. A more general approach is proposed here, referred to as the Sliding MinPD method, that reconstructs evolutionary networks for serially-sampled sequences in the presence of recombination. Results: Sliding MinPD combines distance-based phylogenetic methods with automated recombination detection based on the best-known sliding window approaches to reconstruct serial evolutionary networks. Its performance was evaluated through comprehensive simulation studies and was also applied to a set of serially-sampled HIV sequences from a single patient. The resulting network organizations reveal unique patterns of viral evolution and may help explain the emergence of disease-associated mutants and drug-resistant strains with implications for patient prognosis and treatment strategies. © The Author 2007. Published by Oxford University Press. All rights reserved." @Article{BuendiaNarasimhan2007b,       AUTHOR = {Buendia, Patricia and Narasimhan, Giri},       TITLE = {Sliding MinPD: Building evolutionary networks of serial samples via an automated recombination detection approach},       YEAR = {2007},       JOURNAL = {BIO},       VOLUME = {23},       NUMBER = {22},       PAGES = {2993-3000},       URL = {http://dx.doi.org/10.1093/bioinformatics/btm413},       NOTE = {http://dx.doi.org/10.1093/bioinformatics/btm413},       ANNOTE = {BIBUPDATE : 20071228},       KEYWORDS = {from sequences, phylogenetic network, phylogeny, Program Sliding MinPD, recombination, recombination detection, serial evolutionary networks, software} } 133 Insa Cassens, Patrick Mardulyn and Michel C. Milinkovitch. Evaluating Intraspecific Network Construction Methods Using Simulated Sequence Data: Do Existing Algorithms Outperform the Global Maximum Parsimony Approach? In Systematic Biology, Vol. 54(3):363-372, 2005. Keywords: abstract network, evaluation, from unrooted trees, haplotype network, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program CombineTrees, Program Network, Program TCS, reconstruction, software. Note: http://www.lanevol.org/LANE/publications_files/Cassens_etal_SystBio_2005.pdf.         @Article{CMM2005,       AUTHOR = {Cassens, Insa and Mardulyn, Patrick and Milinkovitch, Michel C.},       TITLE = {Evaluating Intraspecific Network Construction Methods Using Simulated Sequence Data: Do Existing Algorithms Outperform the Global Maximum Parsimony Approach?},       YEAR = {2005},       JOURNAL = {Systematic Biology},       VOLUME = {54},       NUMBER = {3},       PAGES = {363-372},       URL = {http://www.jstor.org/stable/20061240},       NOTE = {http://www.lanevol.org/LANE/publications_files/Cassens_etal_SystBio_2005.pdf},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, evaluation, from unrooted trees, haplotype network, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program CombineTrees, Program Network, Program TCS, reconstruction, software} } 134 Laurent Excoffier and Peter E. Smouse. Using Allele Frequencies and Geographic Subdivision to Reconstruct Gene Trees Within a Species: Molecular Variance Parsimony. In GEN, Vol. 136:343-359, 1994. Keywords: from distances, minimum spanning network, phylogenetic network, phylogeny, Program Arlequin, reconstruction, software. Note: http://www.genetics.org/cgi/content/abstract/136/1/343.         @Article{ExcoffierSmouse1994,       AUTHOR = {Excoffier, Laurent and Smouse, Peter E.},       TITLE = {Using Allele Frequencies and Geographic Subdivision to Reconstruct Gene Trees Within a Species: Molecular Variance Parsimony},       YEAR = {1994},       JOURNAL = {GEN},       VOLUME = {136},       PAGES = {343-359},       NOTE = {http://www.genetics.org/cgi/content/abstract/136/1/343},       ANNOTE = {CITE : },       KEYWORDS = {from distances, minimum spanning network, phylogenetic network, phylogeny, Program Arlequin, reconstruction, software} } 135 Ali Tofigh, Mike Hallett and Jens Lagergren. Simultaneous Identification of Duplications and Lateral Gene Transfers. In TCBB, Vol. 8(2):517-535, 2011. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://dx.doi.org/10.1109/TCBB.2010.14.         Toggle abstract "The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-scenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTL-scenarios is NP-hard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixed-parameter tractable algorithm for finding most parsimonious DTL-scenarios. © 2011 IEEE." @Article{THL2011,       AUTHOR = {Tofigh, Ali and Hallett, Mike and Lagergren, Jens},       TITLE = {Simultaneous Identification of Duplications and Lateral Gene Transfers},       YEAR = {2011},       JOURNAL = {TCBB},       VOLUME = {8},       NUMBER = {2},       PAGES = {517-535},       URL = {http://dx.doi.org/10.1109/TCBB.2010.14},       NOTE = {http://dx.doi.org/10.1109/TCBB.2010.14},       KEYWORDS = {duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction} } 136 Leo van Iersel, Steven Kelk and Matthias Mnich. Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks. In JBCB, Vol. 7(4):597-623, 2009. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction, uniqueness. Note: http://arxiv.org/pdf/0712.2932v2.         @Article{IKM2009,       AUTHOR = {van Iersel, Leo and Kelk, Steven and Mnich, Matthias},       TITLE = {Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks},       YEAR = {2009},       JOURNAL = {JBCB},       VOLUME = {7},       NUMBER = {4},       PAGES = {597-623},       URL = {http://dx.doi.org/10.1142/S0219720009004308},       NOTE = {http://arxiv.org/pdf/0712.2932v2},       ANNOTE = {BIBUPDATE : 20081216},       KEYWORDS = {explicit network, from triplets, galled tree, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, reconstruction, uniqueness} } 137 Daniel H. Huson. Drawing Rooted Phylogenetic Networks. In TCBB, Vol. 6(1):103-109, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program Dendroscope, Program SplitsTree, visualization. Note: http://dx.doi.org/10.1109/TCBB.2008.58.         Toggle abstract "The evolutionary history of a collection of species is usually represented by a phylogenetic tree. Sometimes, phylogenetic networks are used as a means of representing reticulate evolution or of showing uncertainty and incompatibilities in evolutionary datasets. This is often done using unrooted phylogenetic networks such as split networks, due in part, to the availability of software (SplitsTree) for their computation and visualization. In this paper we discuss the problem of drawing rooted phylogenetic networks as cladograms or phylograms in a number of different views that are commonly used for rooted trees. Implementations of the algorithms are available in new releases of the Dendroscope and SplitsTree programs. © 2006 IEEE." @Article{Huson2009,       AUTHOR = {Huson, Daniel H.},       TITLE = {Drawing Rooted Phylogenetic Networks},       YEAR = {2009},       JOURNAL = {TCBB},       VOLUME = {6},       NUMBER = {1},       PAGES = {103-109},       URL = {http://dx.doi.org/10.1109/TCBB.2008.58},       NOTE = {http://dx.doi.org/10.1109/TCBB.2008.58},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, phylogenetic network, phylogeny, Program Dendroscope, Program SplitsTree, visualization} } 138 Andreas W. M. Dress, Katharina Huber, Jacobus Koolen and Vincent Moulton. Compatible decompositions and block realizations of finite metrics. In EJC, Vol. 29(7):1617-1633, 2008. Keywords: abstract network, block realization, from distances, phylogenetic network, phylogeny, realization, reconstruction. Note: http://www.ims.nus.edu.sg/preprints/2007-21.pdf.         Toggle abstract "Given a metric D defined on a finite set X, we define a finite collection D of metrics on X to be a compatible decomposition of D if any two distinct metrics in D are linearly independent (considered as vectors in RX × X), D = ∑d ∈ D d holds, and there exist points x, x′ ∈ X for any two distinct metrics d, d′ in D such that d (x, y) d′ (x′, y) = 0 holds for every y ∈ X. In this paper, we show that such decompositions are in one-to-one correspondence with (isomorphism classes of) block realizations of D, that is, graph realizations G of D for which G is a block graph and for which every vertex in G not labelled by X has degree at least 3 and is a cut point of G. This generalizes a fundamental result in phylogenetic combinatorics that states that a metric D defined on X can be realized by a tree if and only if there exists a compatible decomposition D of D such that all metrics d ∈ D are split metrics, and lays the foundation for a more general theory of metric decompositions that will be explored in future papers. © 2007 Elsevier Ltd. All rights reserved." @Article{DHKM2008,       AUTHOR = {Dress, Andreas W. M. and Huber, Katharina and Koolen, Jacobus and Moulton, Vincent},       TITLE = {Compatible decompositions and block realizations of finite metrics},       YEAR = {2008},       JOURNAL = {EJC},       VOLUME = {29},       NUMBER = {7},       PAGES = {1617-1633},       URL = {http://dx.doi.org/10.1016/j.ejc.2007.10.003},       NOTE = {http://www.ims.nus.edu.sg/preprints/2007-21.pdf},       ANNOTE = {BIBUPDATE : 20080303},       KEYWORDS = {abstract network, block realization, from distances, phylogenetic network, phylogeny, realization, reconstruction} } 139 Tobias Kloepper and Daniel H. Huson. Drawing explicit phylogenetic networks and their integration into SplitsTree. In BMCEB, Vol. 8(22), 2008. Keywords: explicit network, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization. Note: http://dx.doi.org/10.1186/1471-2148-8-22.         Toggle abstract "Background. SplitsTree provides a framework for the calculation of phylogenetic trees and networks. It contains a wide variety of methods for the import/export, calculation and visualization of phylogenetic information. The software is developed in Java and implements a command line tool as well as a graphical user interface. Results. In this article, we present solutions to two important problems in the field of phylogenetic networks. The first problem is the visualization of explicit phylogenetic networks. To solve this, we present a modified version of the equal angle algorithm that naturally integrates reticulations into the layout process and thus leads to an appealing visualization of these networks. The second problem is the availability of explicit phylogenetic network methods for the general user. To advance the usage of explicit phylogenetic networks by biologists further, we present an extension to the SplitsTree framework that integrates these networks. By addressing these two problems, SplitsTree is among the first programs that incorporates implicit and explicit network methods together with standard phylogenetic tree methods in a graphical user interface environment. Conclusion. In this article, we presented an extension of SplitsTree 4 that incorporates explicit phylogenetic networks. The extension provides a set of core classes to handle explicit phylogenetic networks and a visualization of these networks. © 2008 Kloepper and Huson; licensee BioMed Central Ltd." @Article{KloepperHuson2008,       AUTHOR = {Kloepper, Tobias and Huson, Daniel H.},       TITLE = {Drawing explicit phylogenetic networks and their integration into SplitsTree},       YEAR = {2008},       JOURNAL = {BMCEB},       VOLUME = {8},       NUMBER = {22},       URL = {http://dx.doi.org/10.1186/1471-2148-8-22},       NOTE = {http://dx.doi.org/10.1186/1471-2148-8-22},       ANNOTE = {BIBUPDATE : 20080303},       KEYWORDS = {explicit network, phylogenetic network, phylogeny, Program SplitsTree, software, split network, visualization} } 140 Changiz Eslahchi, Mahnaz Habibi, Reza Hassanzadeh and Ehsan Mottaghi. MC-Net: a method for the construction of phylogenetic networks based on the Monte-Carlo method. In BMCEB, Vol. 10:254, 2010. Keywords: abstract network, circular split system, from distances, heuristic, phylogenetic network, Program MC-Net, Program SplitsTree, software, split, split network. Note: http://dx.doi.org/10.1186/1471-2148-10-254.         Toggle abstract "Background. A phylogenetic network is a generalization of phylogenetic trees that allows the representation of conflicting signals or alternative evolutionary histories in a single diagram. There are several methods for constructing these networks. Some of these methods are based on distances among taxa. In practice, the methods which are based on distance perform faster in comparison with other methods. The Neighbor-Net (N-Net) is a distance-based method. The N-Net produces a circular ordering from a distance matrix, then constructs a collection of weighted splits using circular ordering. The SplitsTree which is a program using these weighted splits makes a phylogenetic network. In general, finding an optimal circular ordering is an NP-hard problem. The N-Net is a heuristic algorithm to find the optimal circular ordering which is based on neighbor-joining algorithm. Results. In this paper, we present a heuristic algorithm to find an optimal circular ordering based on the Monte-Carlo method, called MC-Net algorithm. In order to show that MC-Net performs better than N-Net, we apply both algorithms on different data sets. Then we draw phylogenetic networks corresponding to outputs of these algorithms using SplitsTree and compare the results. Conclusions. We find that the circular ordering produced by the MC-Net is closer to optimal circular ordering than the N-Net. Furthermore, the networks corresponding to outputs of MC-Net made by SplitsTree are simpler than N-Net. © 2010 Eslahchi et al; licensee BioMed Central Ltd." @Article{EHHM2010,       AUTHOR = {Eslahchi, Changiz and Habibi, Mahnaz and Hassanzadeh, Reza and Mottaghi, Ehsan},       TITLE = {MC-Net: a method for the construction of phylogenetic networks based on the Monte-Carlo method},       YEAR = {2010},       JOURNAL = {BMCEB},       VOLUME = {10},       PAGES = {254},       URL = {http://dx.doi.org/10.1186/1471-2148-10-254},       NOTE = {http://dx.doi.org/10.1186/1471-2148-10-254},       KEYWORDS = {abstract network, circular split system, from distances, heuristic, phylogenetic network, Program MC-Net, Program SplitsTree, software, split, split network} } 141 Luay Nakhleh. A Metric on the Space of Reduced Phylogenetic Networks. In TCBB, Vol. 7(2), 2010. Keywords: distance between networks, phylogenetic network, phylogeny. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb-Metric.pdf.         Toggle abstract "Phylogenetic networks are leaf-labeled, rooted, acyclic, and directed graphs that are used to model reticulate evolutionary histories. Several measures for quantifying the topological dissimilarity between two phylogenetic networks have been devised, each of which was proven to be a metric on certain restricted classes of phylogenetic networks. A biologically motivated class of phylogenetic networks, namely, reduced phylogenetic networks, was recently introduced. None of the existing measures is a metric on the space of reduced phylogenetic networks. In this paper, we provide a metric on the space of reduced phylogenetic networks that is computable in time polynomial in the size of the networks. © 2006 IEEE." @Article{Nakhleh2010,       AUTHOR = {Nakhleh, Luay},       TITLE = {A Metric on the Space of Reduced Phylogenetic Networks},       YEAR = {2010},       JOURNAL = {TCBB},       VOLUME = {7},       NUMBER = {2},       URL = {http://dx.doi.org/10.1109/TCBB.2009.2},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/tcbb-Metric.pdf},       ANNOTE = {http://doi.ieeecomputersociety.org/10.1109/TCBB.2009.2},       KEYWORDS = {distance between networks, phylogenetic network, phylogeny} } 142 Dan Levy and Lior Pachter. The Neighbor-Net Algorithm. In Advances in Applied Mathematics, Vol. 47(2):240-258, 2011. Keywords: abstract network, circular split system, evaluation, from distances, NeighborNet, phylogenetic network, phylogeny, split network. Note: http://arxiv.org/abs/math/0702515.         Toggle abstract "The neighbor-joining algorithm is a popular phylogenetics method for constructing trees from dissimilarity maps. The neighbor-net algorithm is an extension of the neighbor-joining algorithm and is used for constructing split networks. We begin by describing the output of neighbor-net in terms of the tessellation of M̄0n(R) by associahedra. This highlights the fact that neighbor-net outputs a tree in addition to a circular ordering and we explain when the neighbor-net tree is the neighbor-joining tree. A key observation is that the tree constructed in existing implementations of neighbor-net is not a neighbor-joining tree. Next, we show that neighbor-net is a greedy algorithm for finding circular split systems of minimal balanced length. This leads to an interpretation of neighbor-net as a greedy algorithm for the traveling salesman problem. The algorithm is optimal for Kalmanson matrices, from which it follows that neighbor-net is consistent and has optimal radius 12. We also provide a statistical interpretation for the balanced length for a circular split system as the length based on weighted least squares estimates of the splits. We conclude with applications of these results and demonstrate the implications of our theorems for a recently published comparison of Papuan and Austronesian languages. © 2010 Elsevier Inc. All rights reserved." @Article{LevyPachter2008,       AUTHOR = {Levy, Dan and Pachter, Lior},       TITLE = {The Neighbor-Net Algorithm},       YEAR = {2011},       JOURNAL = {Advances in Applied Mathematics},       VOLUME = {47},       NUMBER = {2},       PAGES = {240-258},       URL = {http://dx.doi.org/10.1016/j.aam.2010.09.002},       NOTE = {http://arxiv.org/abs/math/0702515},       ANNOTE = {BIBUPDATE : 20080321},       KEYWORDS = {abstract network, circular split system, evaluation, from distances, NeighborNet, phylogenetic network, phylogeny, split network} } 143 Leo van Iersel, Steven Kelk, Nela Lekic and Leen Stougie. Approximation algorithms for nonbinary agreement forests. In SIDMA, Vol. 28(1):49-66, 2014. Keywords: agreement forest, approximation, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction. Note: http://arxiv.org/abs/1210.3211.         Toggle abstract "Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest (maaf) problem has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of maf has a polynomial-time 4-approximation and a fixedparameter tractable (exact) algorithm that runs in O(4opoly(n)) time, where n = |X| and k is the number of components of the agreement forest minus one. Moreover, we show that a c-approximation algorithm for nonbinary maf and a d-approximation algorithm for the classical problem Directed Feedback Vertex Set (dfvs) can be combined to yield a d(c+3)-approximation for nonbinary maaf. The algorithms for maf have been implemented and made publicly available. © 2014 Society for Industrial and Applied Mathematics." @Article{IKLS2014,       AUTHOR = {van Iersel, Leo and Kelk, Steven and Lekic, Nela and Stougie, Leen},       TITLE = {Approximation algorithms for nonbinary agreement forests},       YEAR = {2014},       JOURNAL = {SIDMA},       VOLUME = {28},       NUMBER = {1},       PAGES = {49-66},       URL = {http://dx.doi.org/10.1137/120903567},       NOTE = {http://arxiv.org/abs/1210.3211},       KEYWORDS = {agreement forest, approximation, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, reconstruction} } 144 Steven M. Woolley, David Posada and Keith A. Crandall. A Comparison of Phylogenetic Network Methods Using Computer Simulation. In PLoS ONE, Vol. 3(4):e1913, 2008. Keywords: abstract network, distance between networks, evaluation, median network, MedianJoining, minimum spanning network, NeighborNet, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program CombineTrees, Program Network, Program SHRUB, Program SplitsTree, Program TCS, split decomposition. Note: http://dx.doi.org/10.1371/journal.pone.0001913.         Toggle abstract "Background: We present a series of simulation studies that explore the relative performance of several phylogenetic network approaches (statistical parsimony, split decomposition, union of maximum parsimony trees, neighbor-net, simulated history recombination upper bound, median-joining, reduced median joining and minimum spanning network) compared to standard tree approaches (neighbor-joining and maximum parsimony) in the presence and absence of recombination. Principal Findings: In the absence of recombination, all methods recovered the correct topology and branch lengths nearly all of the time when the subtitution rate was low, except for minimum spanning networks, which did considerably worse. At a higher substitution rate, maximum parsimony and union of maximum parsimony trees were the most accurate. With recombination, the ability to infer the correct topology was halved for all methods and no method could accurately estimate branch lengths. Conclusions: Our results highlight the need for more accurate phylogenetic network methods and the importance of detecting and accounting for recombination in phylogenetic studies. Furthermore, we provide useful information for choosing a network algorithm and a framework in which to evaluate improvements to existing methods and novel algorithms developed in the future. © 2008 Woolley et al." @Article{WPC2008,       AUTHOR = {Woolley, Steven M. and Posada, David and Crandall, Keith A.},       TITLE = {A Comparison of Phylogenetic Network Methods Using Computer Simulation},       YEAR = {2008},       JOURNAL = {PLoS ONE},       VOLUME = {3},       NUMBER = {4},       PAGES = {e1913},       URL = {http://dx.doi.org/10.1371/journal.pone.0001913},       NOTE = {http://dx.doi.org/10.1371/journal.pone.0001913},       ANNOTE = {BIBUPDATE : 20080421},       KEYWORDS = {abstract network, distance between networks, evaluation, median network, MedianJoining, minimum spanning network, NeighborNet, parsimony, phylogenetic network, phylogeny, Program Arlequin, Program CombineTrees, Program Network, Program SHRUB, Program SplitsTree, Program TCS, split decomposition} } 145 Bastienne Vriesendorp and Freek T. Bakker. Reconstructing patterns of reticulate evolution in angiosperms: what can we do? In Taxon, Vol. 54(3):593-604, 2005. Note: results cited in http://library.wur.nl/wda/dissertations/dis4239.pdf.         @Article{VriesendorpBakker2005,       AUTHOR = {Vriesendorp, Bastienne and Bakker, Freek T.},       TITLE = {Reconstructing patterns of reticulate evolution in angiosperms: what can we do?},       YEAR = {2005},       JOURNAL = {Taxon},       VOLUME = {54},       NUMBER = {3},       PAGES = {593-604},       URL = {http://dx.doi.org/10.2307/25065417},       NOTE = {results cited in http://library.wur.nl/wda/dissertations/dis4239.pdf},       ANNOTE = {CITE : } } 146 Simone Linz and Charles Semple. Hybridization in non-binary trees. In TCBB, Vol. 6(1):30-45, 2009. Keywords: agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, reconstruction. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/LS08.pdf, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw03/1220/linz/.         @Article{LinzSemple2009,       AUTHOR = {Linz, Simone and Semple, Charles},       TITLE = {Hybridization in non-binary trees},       YEAR = {2009},       JOURNAL = {TCBB},       VOLUME = {6},       NUMBER = {1},       PAGES = {30-45},       URL = {http://dx.doi.org/10.1109/TCBB.2008.86},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/LS08.pdf, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw03/1220/linz/},       ANNOTE = {CITE : },       KEYWORDS = {agreement forest, FPT, from rooted trees, hybridization, phylogenetic network, phylogeny, reconstruction} } 147 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. A Distance Metric for a Class of Tree-Sibling Phylogenetic Networks. In BIO, Vol. 24(13):1481-1488, 2008. Keywords: distance between networks, phylogenetic network, phylogeny, polynomial, tree sibling network. Note: http://dx.doi.org/10.1093/bioinformatics/btn231.         Toggle abstract "Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences. Results: We present in this articlea distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data. © 2008 The Author(s)." @Article{CLRV2008b,       AUTHOR = {Cardona, Gabriel and Llabr{\~A}�s, Merc{\~A}� and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {A Distance Metric for a Class of Tree-Sibling Phylogenetic Networks},       YEAR = {2008},       JOURNAL = {BIO},       VOLUME = {24},       NUMBER = {13},       PAGES = {1481-1488},       URL = {http://dx.doi.org/10.1093/bioinformatics/btn231},       NOTE = {http://dx.doi.org/10.1093/bioinformatics/btn231},       ANNOTE = {BIBUPDATE : 20080505, 20080520},       KEYWORDS = {distance between networks, phylogenetic network, phylogeny, polynomial, tree sibling network} } 148 James B. Whitfield, Sydney A. Cameron, Daniel H. Huson and Mike Steel. Filtered Z-Closure Supernetworks for Extracting and Visualizing Recurrent Signal from Incongruent Gene Trees. In Systematic Biology, Vol. 57(6):939-947, 2008. Keywords: abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, split, split network, supernetwork. Note: http://www.life.uiuc.edu/scameron/pdfs/Filtered%20Z-closure%20SystBiol.pdf.         @Article{WCHS2008,       AUTHOR = {Whitfield, James B. and Cameron, Sydney A. and Huson, Daniel H. and Steel, Mike},       TITLE = {Filtered Z-Closure Supernetworks for Extracting and Visualizing Recurrent Signal from Incongruent Gene Trees},       YEAR = {2008},       JOURNAL = {Systematic Biology},       VOLUME = {57},       NUMBER = {6},       PAGES = {939-947},       URL = {http://dx.doi.org/10.1080/10635150802552849},       NOTE = {http://www.life.uiuc.edu/scameron/pdfs/Filtered%20Z-closure%20SystBiol.pdf},       ANNOTE = {CITE : },       KEYWORDS = {abstract network, from unrooted trees, phylogenetic network, phylogeny, Program SplitsTree, split, split network, supernetwork} } 149 Paul Marjoram and Robert C. Griffiths. Ancestral inference from samples of DNA sequences with recombination. In JCB, Vol. 3(4):479-502, 1996. Keywords: ARG, phylogenetic network, phylogeny, statistical model. Note: http://www.math.canterbury.ac.nz/~r.sainudiin/recomb/JCB_paper.pdf.         @Article{GriffithsMarjoram1996,       AUTHOR = {Marjoram, Paul and Griffiths, Robert C.},       TITLE = {Ancestral inference from samples of DNA sequences with recombination},       YEAR = {1996},       JOURNAL = {JCB},       VOLUME = {3},       NUMBER = {4},       PAGES = {479-502},       URL = {http://dx.doi.org/10.1089/cmb.1996.3.479},       NOTE = {http://www.math.canterbury.ac.nz/~r.sainudiin/recomb/JCB_paper.pdf},       ANNOTE = {CITE : },       KEYWORDS = {ARG, phylogenetic network, phylogeny, statistical model} } 150 Ingo Althöfer. On optimal realizations of finite metric spaces by graphs. In Discrete and Computational Geometry, Vol. 3(1):103-122, 1986. Keywords: NP complete, optimal realization, realization. Note: http://dx.doi.org/10.1007/BF02187901.         Toggle abstract "Graph realizations of finite metric spaces have widespread applications, for example, in biology, economics, and information theory. The main results of this paper are: 1. Finding optimal realizations of integral metrics (which means all distances are integral) is NP-complete. 2. There exist metric spaces with a continuum of optimal realizations. Furthermore, two conditions necessary for a weighted graph to be an optimal realization are given and an extremal problem arising in connection with the realization problem is investigated. © 1988 Springer-Verlag New York Inc." @Article{Althoefer1986,       AUTHOR = {Alth{\~A}�fer, Ingo},       TITLE = {On optimal realizations of finite metric spaces by graphs},       YEAR = {1986},       JOURNAL = {Discrete and Computational Geometry},       VOLUME = {3},       NUMBER = {1},       PAGES = {103-122},       URL = {http://dx.doi.org/10.1007/BF02187901},       NOTE = {http://dx.doi.org/10.1007/BF02187901},       ANNOTE = {BIBUPDATE : 20080513},       KEYWORDS = {NP complete, optimal realization, realization} } 151 Kim McBreen and Peter J. Lockhart. Reconstructing reticulate evolutionary histories of plants. In Trends in Plant Science, Vol. 11(8):103-122, 2006. Note: http://www.aseanbiodiversity.info/Abstract/51006032.pdf.         @Article{McBreenLockhart2006,       AUTHOR = {McBreen, Kim and Lockhart, Peter J.},       TITLE = {Reconstructing reticulate evolutionary histories of plants},       YEAR = {2006},       JOURNAL = {Trends in Plant Science},       VOLUME = {11},       NUMBER = {8},       PAGES = {103-122},       URL = {http://dx.doi.org/10.1016/j.tplants.2006.06.004},       NOTE = {http://www.aseanbiodiversity.info/Abstract/51006032.pdf},       ANNOTE = {BIBUPDATE : 20080513} } 152 Joanna L. Davies, Frantisek Simancík, Rune Lyngsø, Thomas Mailund and Jotun Hein. On Recombination-Induced Multiple and Simultaneous Coalescent Events. In GEN, Vol. 177:2151-2160, 2007. Keywords: coalescent, phylogenetic network, phylogeny, recombination, statistical model. Note: http://dx.doi.org/10.1534/genetics.107.071126.         Toggle abstract "Coalescent theory deals with the dynamics of how sampled genetic material has spread through a population from a single ancestor over many generations and is ubiquitous in contemporary molecular population genetics. Inherent in most applications is a continuous-time approximation that is derived under the assumption that sample size is small relative to the actual population size. In effect, this precludes multiple and simultaneous coalescent events that take place in the history of large samples. If sequences do not recombine, the number of sequences ancestral to a large sample is reduced sufficiently after relatively few generations such that use of the continuous-time approximation is justified. However, in tracing the history of large chromosomal segments, a large recombination rate per generation will consistently maintain a large number of ancestors. This can create a major disparity between discrete-time and continuous-time models and we analyze its importance, illustrated with model parameters typical of the human genome. The presence of gene conversion exacerbates the disparity and could seriously undermine applications of coalescent theory to complete genomes. However, we show that multiple and simultaneous coalescent events influence global quantities, such as total number of ancestors, but have negligible effect on local quantities, such as linkage disequilibrium. Reassuringly, most applications of the coalescent model with recombination (including association mapping) focus on local quantities. Copyright © 2007 by the Genetics Society of America." @Article{DSLMH2007,       AUTHOR = {Davies, Joanna L. and Simanc{\~A}�k, Frantisek and Lyngs{\~A}�, Rune and Mailund, Thomas and Hein, Jotun},       TITLE = {On Recombination-Induced Multiple and Simultaneous Coalescent Events},       YEAR = {2007},       JOURNAL = {GEN},       VOLUME = {177},       PAGES = {2151-2160},       URL = {http://dx.doi.org/10.1534/genetics.107.071126},       NOTE = {http://dx.doi.org/10.1534/genetics.107.071126},       ANNOTE = {CITE : },       KEYWORDS = {coalescent, phylogenetic network, phylogeny, recombination, statistical model} } 153 Shlomo Moran, Sagi Snir and Wing-Kin Sung. Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower bounds. In ACM Transactions on Algorithms, Vol. 7(4), 2011. Keywords: evaluation, galled tree, phylogenetic network. Note: http://www.cs.technion.ac.il/~moran/r/PS/gnets-TOA-7Feb2007.pdf.         Toggle abstract "A coloring of a graph is convex if the vertices that pertain to any color induce a connected subgraph; a partial coloring (which assigns colors to a subset of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring has applications in fields such as phylogenetics, communication or transportation networks, etc. When a coloring of a graph is not convex, a natural question is how far it is from a convex one. This problem is denoted as convex recoloring (CR).While the initial works on CR defined and studied the problem on trees, recent efforts aim at either generalizing the underlying graphs or specializing the input colorings. In this work, we extend the underlying graph and the input coloring to partially colored galled networks. We show that although determining whether a coloring is convex on an arbitrary network is hard, it can be found efficiently on galled networks. We present a fixed parameter tractable algorithm that finds the recoloring distance of such a network whose running time is quadratic in the network size and exponential in that distance. This complexity is achieved by amortized analysis that uses a novel technique for contracting colored graphs that seems to be of independent interest. © 2011 ACM." @Article{MSS2011,       AUTHOR = {Moran, Shlomo and Snir, Sagi and Sung, Wing-Kin},       TITLE = {Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower bounds},       YEAR = {2011},       JOURNAL = {ACM Transactions on Algorithms},       VOLUME = {7},       NUMBER = {4},       URL = {http://dx.doi.org/10.1145/2000807.2000810},       NOTE = {http://www.cs.technion.ac.il/~moran/r/PS/gnets-TOA-7Feb2007.pdf},       ANNOTE = {BIBUPDATE : 20080605, http://www.cs.technion.ac.il/~moran/r/PS/TALG-20Nov2008.pdf},       KEYWORDS = {evaluation, galled tree, phylogenetic network} } 154 Sagi Snir and Tamir Tuller. The NET-HMM approach: Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In JBCB, Vol. 7(4):625-644, 2009. Keywords: explicit network, from sequences, HMM, lateral gene transfer, likelihood, phylogenetic network, phylogeny, statistical model. Note: http://research.haifa.ac.il/~ssagi/published%20papers/Snir-NET-HMM-JBCB-2009.pdf.         Toggle abstract "Horizontal gene transfer (HGT) is the event of transferring genetic material from one lineage in the evolutionary tree to a different lineage. HGT plays a major role in bacterial genome diversification and is a significant mechanism by which bacteria develop resistance to antibiotics. Although the prevailing assumption is of complete HGT, cases of partial HGT (which are also named chimeric HGT) where only part of a gene is horizontally transferred, have also been reported, albeit less frequently. In this work we suggest a new probabilistic model, the NET-HMM, for analyzing and modeling phylogenetic networks. This new model captures the biologically realistic assumption that neighboring sites of DNA or amino acid sequences are not independent, which increases the accuracy of the inference. The model describes the phylogenetic network as a Hidden Markov Model (HMM), where each hidden state is related to one of the network's trees. One of the advantages of the NET-HMM is its ability to infer partial HGT as well as complete HGT. We describe the properties of the NET-HMM, devise efficient algorithms for solving a set of problems related to it, and implement them in software. We also provide a novel complementary significance test for evaluating the fitness of a model (NET-HMM) to a given dataset. Using NET-HMM, we are able to answer interesting biological questions, such as inferring the length of partial HGT's and the affected nucleotides in the genomic sequences, as well as inferring the exact location of HGT events along the tree branches. These advantages are demonstrated through the analysis of synthetical inputs and three different biological inputs. © 2009 Imperial College Press." @Article{SnirTuller2009,       AUTHOR = {Snir, Sagi and Tuller, Tamir},       TITLE = {The NET-HMM approach: Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models},       YEAR = {2009},       JOURNAL = {JBCB},       VOLUME = {7},       NUMBER = {4},       PAGES = {625-644},       URL = {http://dx.doi.org/10.1142/S021972000900428X},       NOTE = {http://research.haifa.ac.il/~ssagi/published%20papers/Snir-NET-HMM-JBCB-2009.pdf},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, from sequences, HMM, lateral gene transfer, likelihood, phylogenetic network, phylogeny, statistical model} } 155 Stefan Grünewald, Katharina Huber, Vincent Moulton, Charles Semple and Andreas Spillner. Characterizing weak compatibility in terms of weighted quartets. In Advances in Applied Mathematics, Vol. 42(3):329-341, 2009. Keywords: abstract network, characterization, from quartets, split network, weak hierarchy. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/GHMSS08.pdf, slides at http://www.lirmm.fr/miep08/slides/12_02_huber.pdf.         @Article{GHMSS2009,       AUTHOR = {Gr{\~A}�newald, Stefan and Huber, Katharina and Moulton, Vincent and Semple, Charles and Spillner, Andreas},       TITLE = {Characterizing weak compatibility in terms of weighted quartets},       YEAR = {2009},       JOURNAL = {Advances in Applied Mathematics},       VOLUME = {42},       NUMBER = {3},       PAGES = {329-341},       URL = {http://dx.doi.org/10.1016/j.aam.2008.07.002},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/GHMSS08.pdf, slides at http://www.lirmm.fr/miep08/slides/12_02_huber.pdf},       ANNOTE = {BIBUPDATE : 20080722},       KEYWORDS = {abstract network, characterization, from quartets, split network, weak hierarchy} } 156 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Metrics for phylogenetic networks I: Generalizations of the Robinson-Foulds metric. In TCBB, Vol. 6(1):46-61, 2009. Keywords: distance between networks, explicit network, phylogenetic network, phylogeny, time consistent network, tree-child network, tripartition distance. Note: http://dx.doi.org/10.1109/TCBB.2008.70.         Toggle abstract "The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the first in a series of papers devoted to the analysis and comparison of metrics for tree-child time consistent phylogenetic networks on the same set of taxa. In this paper, we study three metrics that have already been introduced in the literature: the Robinson-Foulds distance, the tripartitions distance and the $mu$-distance. They generalize to networks the classical Robinson-Foulds or partition distance for phylogenetic trees. We analyze the behavior of these metrics by studying their least and largest values and when they achieve them. As a by-product of this study, we obtain tight bounds on the size of a tree-child time consistent phylogenetic network. © 2006 IEEE." @Article{CLRV2009a,       AUTHOR = {Cardona, Gabriel and Llabr{\~A}�s, Merc{\~A}� and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {Metrics for phylogenetic networks I: Generalizations of the Robinson-Foulds metric},       YEAR = {2009},       JOURNAL = {TCBB},       VOLUME = {6},       NUMBER = {1},       PAGES = {46-61},       URL = {http://dx.doi.org/10.1109/TCBB.2008.70},       NOTE = {http://dx.doi.org/10.1109/TCBB.2008.70},       ANNOTE = {BIBUPDATE : 20080725},       KEYWORDS = {distance between networks, explicit network, phylogenetic network, phylogeny, time consistent network, tree-child network, tripartition distance} } 157 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Metrics for phylogenetic networks II: Nodal and triplets metrics. In TCBB, Vol. 6(3):454-469, 2009. Keywords: distance between networks, phylogenetic network, phylogeny. Note: http://dx.doi.org/10.1109/TCBB.2008.127.         Toggle abstract "The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the second in a series of papers devoted to the analysis and comparison of metrics for tree-child time consistent phylogenetic networks on the same set of taxa. In this paper, we generalize to phylogenetic networks two metrics that have already been introduced in the literature for phylogenetic trees: the nodal distance and the triplets distance. We prove that they are metrics on any class of tree- child time consistent phylogenetic networks on the same set of taxa, as well as some basic properties for them. To prove these results, we introduce a reduction/expansion procedure that can be used not only to establish properties of tree-child time consistent phylogenetic networks by induction, but also to generate all tree-child time consistent phylogenetic networks with a given number of leaves. © 2009 IEEE." @Article{CLRV2009b,       AUTHOR = {Cardona, Gabriel and Llabr{\~A}�s, Merc{\~A}� and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {Metrics for phylogenetic networks II: Nodal and triplets metrics},       YEAR = {2009},       JOURNAL = {TCBB},       VOLUME = {6},       NUMBER = {3},       PAGES = {454-469},       URL = {http://dx.doi.org/10.1109/TCBB.2008.127},       NOTE = {http://dx.doi.org/10.1109/TCBB.2008.127},       ANNOTE = {BIBUPDATE : 20080725},       KEYWORDS = {distance between networks, phylogenetic network, phylogeny} } 158 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Path lengths in tree-child time consistent hybridization networks. In Information Sciences, Vol. 180(3):366-383, 2010. Keywords: distance between networks, phylogenetic network, phylogeny, time consistent network, tree-child network. Note: http://arxiv.org/abs/0807.0087?context=cs.CE.         Toggle abstract "Hybridization networks are representations of evolutionary histories that allow for the inclusion of reticulate events like recombinations, hybridizations, or lateral gene transfers. The recent growth in the number of hybridization network reconstruction algorithms has led to an increasing interest in the definition of metrics for their comparison that can be used to assess the accuracy or robustness of these methods. In this paper we establish some basic results that make it possible the generalization to tree-child time consistent (TCTC) hybridization networks of some of the oldest known metrics for phylogenetic trees: those based on the comparison of the vectors of path lengths between leaves. More specifically, we associate to each hybridization network a suitably defined vector of 'splitted' path lengths between its leaves, and we prove that if two TCTC hybridization networks have the same such vectors, then they must be isomorphic. Thus, comparing these vectors by means of a metric for real-valued vectors defines a metric for TCTC hybridization networks. We also consider the case of fully resolved hybridization networks, where we prove that simpler, 'non-splitted' vectors can be used. © 2009 Elsevier Inc. All rights reserved." @Article{CLRV2010b,       AUTHOR = {Cardona, Gabriel and Llabr{\~A}�s, Merc{\~A}� and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {Path lengths in tree-child time consistent hybridization networks},       YEAR = {2010},       JOURNAL = {Information Sciences},       VOLUME = {180},       NUMBER = {3},       PAGES = {366-383},       URL = {http://dx.doi.org/10.1016/j.ins.2009.09.013},       NOTE = {http://arxiv.org/abs/0807.0087?context=cs.CE},       ANNOTE = {BIBUPDATE : 20080725},       KEYWORDS = {distance between networks, phylogenetic network, phylogeny, time consistent network, tree-child network} } 159 Cuong Than, Derek Ruths and Luay Nakhleh. PhyloNet: A Software Package for Analyzing and Reconstructing Reticulate Evolutionary Relationships. In BMCB, Vol. 9(322), 2008. Keywords: Program PhyloNet, software. Note: http://dx.doi.org/10.1186/1471-2105-9-322.         Toggle abstract "Background: Phylogenies, i.e., the evolutionary histories of groups of taxa, play a major role in representing the interrelationships among biological entities. Many software tools for reconstructing and evaluating such phylogenies have been proposed, almost all of which assume the underlying evolutionary history to be a tree. While trees give a satisfactory first-order approximation for many families of organisms, other families exhibit evolutionary mechanisms that cannot be represented by trees. Processes such as horizontal gene transfer (HGT), hybrid speciation, and interspecific recombination, collectively referred to as reticulate evolutionary events, result in networks, rather than trees, of relationships. Various software tools have been recently developed to analyze reticulate evolutionary relationships, which include SplitsTree4, LatTrans, EEEP, HorizStory, and T-REX. Results: In this paper, we report on the PhyloNet software package, which is a suite of tools for analyzing reticulate evolutionary relationships, or evolutionary networks, which are rooted, directed, acyclic graphs, leaf-labeled by a set of taxa. These tools can be classified into four categories: (1) evolutionary network representation: reading/writing evolutionary networks in a newly devised compact form; (2) evolutionary network characterization: analyzing evolutionary networks in terms of three basic building blocks - trees, clusters, and tripartitions; (3) evolutionary network comparison: comparing two evolutionary networks in terms of topological dissimilarities, as well as fitness to sequence evolution under a maximum parsimony criterion; and (4) evolutionary network reconstruction: reconstructing an evolutionary network from a species tree and a set of gene trees. Conclusion: The software package, PhyloNet, offers an array of utilities to allow for efficient and accurate analysis of evolutionary networks. The software package will help significantly in analyzing large data sets, as well as in studying the performance of evolutionary network reconstruction methods. Further, the software package supports the proposed eNewick format for compact representation of evolutionary networks, a feature that allows for efficient interoperability of evolutionary network software tools. Currently, all utilities in PhyloNet are invoked on the command line. © 2008 Than et al; licensee BioMed Central Ltd." @Article{TRN2008,       AUTHOR = {Than, Cuong and Ruths, Derek and Nakhleh, Luay},       TITLE = {PhyloNet: A Software Package for Analyzing and Reconstructing Reticulate Evolutionary Relationships},       YEAR = {2008},       JOURNAL = {BMCB},       VOLUME = {9},       NUMBER = {322},       URL = {http://dx.doi.org/10.1186/1471-2105-9-322},       NOTE = {http://dx.doi.org/10.1186/1471-2105-9-322},       ANNOTE = {BIBUPDATE : 20080731},       KEYWORDS = {Program PhyloNet, software} } 160 Iyad A. Kanj, Luay Nakhleh, Cuong Than and Ge Xia. Seeing the Trees and Their Branches in the Network is Hard. In TCS, Vol. 401:153-164, 2008. Keywords: evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcs08.pdf.         @Article{KNTX2008,       AUTHOR = {Kanj, Iyad A. and Nakhleh, Luay and Than, Cuong and Xia, Ge},       TITLE = {Seeing the Trees and Their Branches in the Network is Hard},       YEAR = {2008},       JOURNAL = {TCS},       VOLUME = {401},       PAGES = {153-164},       URL = {http://dx.doi.org/10.1016/j.tcs.2008.04.019},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/tcs08.pdf},       ANNOTE = {BIBUPDATE : },       KEYWORDS = {evaluation, from network, from rooted trees, NP complete, phylogenetic network, phylogeny, tree containment} } 161 Barbara R. Holland, Steffi Benthin, Peter J. Lockhart, Vincent Moulton and Katharina Huber. Using supernetworks to distinguish hybridization from lineage-sorting. In BMCEB, Vol. 8(202), 2008. Keywords: explicit network, from unrooted trees, hybridization, lineage sorting, phylogenetic network, phylogeny, reconstruction, supernetwork. Note: http://dx.doi.org/10.1186/1471-2148-8-202.         Toggle abstract "Background. A simple and widely used approach for detecting hybridization in phylogenies is to reconstruct gene trees from independent gene loci, and to look for gene tree incongruence. However, this approach may be confounded by factors such as poor taxon-sampling and/or incomplete lineage-sorting. Results. Using coalescent simulations, we investigated the potential of supernetwork methods to differentiate between gene tree incongruence arising from taxon sampling and incomplete lineage-sorting as opposed to hybridization. For few hybridization events, a large number of independent loci, and well-sampled taxa across these loci, we found that it was possible to distinguish incomplete lineage-sorting from hybridization using the filtered Z-closure and Q-imputation supernetwork methods. Moreover, we found that the choice of supernetwork method was less important than the choice of filtering, and that count-based filtering was the most effective filtering technique. Conclusion. Filtered supernetworks provide a tool for detecting and identifying hybridization events in phylogenies, a tool that should become increasingly useful in light of current genome sequencing initiatives and the ease with which large numbers of independent gene loci can be determined using new generation sequencing technologies. © 2008 Holland et al; licensee BioMed Central Ltd." @Article{HBLMH2008,       AUTHOR = {Holland, Barbara R. and Benthin, Steffi and Lockhart, Peter J. and Moulton, Vincent and Huber, Katharina},       TITLE = {Using supernetworks to distinguish hybridization from lineage-sorting},       YEAR = {2008},       JOURNAL = {BMCEB},       VOLUME = {8},       NUMBER = {202},       URL = {http://dx.doi.org/10.1186/1471-2148-8-202},       NOTE = {http://dx.doi.org/10.1186/1471-2148-8-202},       ANNOTE = {BIBUPDATE : 20080816},       KEYWORDS = {explicit network, from unrooted trees, hybridization, lineage sorting, phylogenetic network, phylogeny, reconstruction, supernetwork} } 162 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. On Nakhleh's metric for reduced phylogenetic networks. In TCBB, Vol. 6(4):629-638, 2009. Keywords: distance between networks, phylogenetic network, phylogeny. Note: Preliminary versions: http://arxiv.org/abs/0809.0110 and http://arxiv.org/abs/0801.2354v1.         Toggle abstract "We prove that Nakhleh's metric for reduced phylogenetic networks is also a metric on the classes of tree-child phylogenetic networks, semibinary tree-sibling time consistent phylogenetic networks, and multilabeled phylogenetic trees. We also prove that it separates distinguishable phylogenetic networks. In this way, it becomes the strongest dissimilarity measure for phylogenetic networks available so far. Furthermore, we propose a generalization of that metric that separates arbitrary phylogenetic networks. © 2009 IEEE." @Article{CLRV2009d,       AUTHOR = {Cardona, Gabriel and Llabr{\~A}�s, Merc{\~A}� and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {On Nakhleh's metric for reduced phylogenetic networks},       YEAR = {2009},       JOURNAL = {TCBB},       VOLUME = {6},       NUMBER = {4},       PAGES = {629-638},       URL = {http://dx.doi.org/10.1109/TCBB.2009.33},       NOTE = {Preliminary versions: http://arxiv.org/abs/0809.0110 and http://arxiv.org/abs/0801.2354v1},       ANNOTE = {BIBUPDATE : 20080925},       KEYWORDS = {distance between networks, phylogenetic network, phylogeny} } 163 Miguel Arenas, Gabriel Valiente and David Posada. Characterization of reticulate networks based on the coalescent with recombination. In MBE, Vol. 25(12):2517-2520, 2008. Keywords: coalescent, evaluation, explicit network, galled tree, phylogenetic network, phylogeny, Program Recodon, regular network, simulation, tree sibling network, tree-child network. Note: http://dx.doi.org/10.1093/molbev/msn219.         Toggle abstract "Phylogenetic networks aim to represent the evolutionary history of taxa. Within these, reticulate networks are explicitly able to accommodate evolutionary events like recombination, hybridization, or lateral gene transfer. Although several metrics exist to compare phylogenetic networks, they make several assumptions regarding the nature of the networks that are not likely to be fulfilled by the evolutionary process. In order to characterize the potential disagreement between the algorithms and the biology, we have used the coalescent with recombination to build the type of networks produced by reticulate evolution and classified them as regular, tree sibling, tree child, or galled trees. We show that, as expected, the complexity of these reticulate networks is a function of the population recombination rate. At small recombination rates, most of the networks produced are already more complex than regular or tree sibling networks, whereas with moderate and large recombination rates, no network fit into any of the standard classes. We conclude that new metrics still need to be devised in order to properly compare two phylogenetic networks that have arisen from reticulating evolutionary process. © 2008 The Authors." @Article{AVP2008,       AUTHOR = {Arenas, Miguel and Valiente, Gabriel and Posada, David},       TITLE = {Characterization of reticulate networks based on the coalescent with recombination},       YEAR = {2008},       JOURNAL = {MBE},       VOLUME = {25},       NUMBER = {12},       PAGES = {2517-2520},       URL = {http://dx.doi.org/10.1093/molbev/msn219},       NOTE = {http://dx.doi.org/10.1093/molbev/msn219},       ANNOTE = {BIBUPDATE : 20081001},       KEYWORDS = {coalescent, evaluation, explicit network, galled tree, phylogenetic network, phylogeny, Program Recodon, regular network, simulation, tree sibling network, tree-child network} } 164 Daniel H. Huson. What If I Don't Have a Tree? Split Decomposition and Related Models. In Current Protocols in Bioinformatics, Vol. Unit 6.7, 2003. Keywords: abstract network, phylogenetic network, Program SplitsTree, software, split decomposition, split network. Note: http://dx.doi.org/10.1002/0471250953.bi0607s01.         @Article{Huson2003,       AUTHOR = {Huson, Daniel H.},       TITLE = {What If I Don't Have a Tree? Split Decomposition and Related Models},       YEAR = {2003},       JOURNAL = {Current Protocols in Bioinformatics},       VOLUME = {Unit 6.7},       URL = {http://dx.doi.org/10.1002/0471250953.bi0607s01},       NOTE = {http://dx.doi.org/10.1002/0471250953.bi0607s01},       ANNOTE = {BIBUPDATE : 20081011},       KEYWORDS = {abstract network, phylogenetic network, Program SplitsTree, software, split decomposition, split network} } 165 Gabriel Cardona, Francesc Rosselló and Gabriel Valiente. Extended Newick: It is Time for a Standard Representation. In BMCB, Vol. 9:532, 2008. Keywords: evaluation, explicit network, phylogenetic network, Program Bio PhyloNetwork, Program Dendroscope, Program NetGen, Program PhyloNet, Program SplitsTree, Program TCS, visualization. Note: http://bioinfo.uib.es/media/uploaded/bmc-2008-enewick-sub.pdf.         @Article{CRV2008c,       AUTHOR = {Cardona, Gabriel and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {Extended Newick: It is Time for a Standard Representation},       YEAR = {2008},       JOURNAL = {BMCB},       VOLUME = {9},       PAGES = {532},       URL = {http://dx.doi.org/10.1186/1471-2105-9-532},       NOTE = {http://bioinfo.uib.es/media/uploaded/bmc-2008-enewick-sub.pdf},       ANNOTE = {BIBUPDATE : 20081011, 20081216},       KEYWORDS = {evaluation, explicit network, phylogenetic network, Program Bio PhyloNetwork, Program Dendroscope, Program NetGen, Program PhyloNet, Program SplitsTree, Program TCS, visualization} } 166 Supriya Munshaw and Thomas B. Kepler. An Information-Theoretic Method for the Treatment of Plural Ancestry in Phylogenetics. In MBE, Vol. 25(6):1199-1208, 2008. Keywords: explicit network, from sequences, heuristic, phylogenetic network, reconstruction, simulated annealing, software. Note: http://dx.doi.org/10.1093/molbev/msn066.         Toggle abstract "In the presence of recombination and gene conversion, a given genomic segment may inherit information from 2 distinct immediate ancestors. The importance of this type of molecular inheritance has become increasingly clear over the years, and the potential for erroneous inference when it is not accounted for in the statistical model is well documented. Yet, the inclusion of plural ancestry (PA) in phylogenetic analysis is still not routine. This omission is due to the greater difficulty of phylogenetic inference on general acyclic graphs compared that on with trees and the accompanying computational burden. We have developed a technique for phylogenetic inference in the presence of PA based on the principle of minimum description length, which assigns a cost - the description length - to each network topology given the observed sequence data. The description length combines the cost of poor data fit and model complexity in terms of information. This device allows us to search through network topologies to minimize the total description length. By comparing the best models obtained with and without PA, one can determine whether or not recombination has played an active role in the evolution of the genes under investigation, identify those genes that appear to be mosaic, and infer the phylogenetic network that best represents the history of the alignment. We show that the method performs well on simulated data and demonstrate its application on HIV env gene sequence data from 8 human subjects. The software implementation of the method is available upon request. © The Author 2008. Published by Oxford University Press on behalf of the Society for Molecular Biology and Evolution. All rights reserved." @Article{MunshawKepler2008,       AUTHOR = {Munshaw, Supriya and Kepler, Thomas B.},       TITLE = {An Information-Theoretic Method for the Treatment of Plural Ancestry in Phylogenetics},       YEAR = {2008},       JOURNAL = {MBE},       VOLUME = {25},       NUMBER = {6},       PAGES = {1199-1208},       URL = {http://dx.doi.org/10.1093/molbev/msn066},       NOTE = {http://dx.doi.org/10.1093/molbev/msn066},       ANNOTE = {CITE : },       KEYWORDS = {explicit network, from sequences, heuristic, phylogenetic network, reconstruction, simulated annealing, software} } 167 Miguel Arenas and David Posada. Recodon: Coalescent simulation of coding DNA sequences with recombination, migration and demography. In BMCB, Vol. 8(458), 2008. Keywords: coalescent, generation, Program Recodon, software. Note: http://dx.doi.org/10.1186/1471-2105-8-458.         Toggle abstract "Background: Coalescent simulations have proven very useful in many population genetics studies. In order to arrive to meaningful conclusions, it is important that these simulations resemble the process of molecular evolution as much as possible. To date, no single coalescent program is able to simulate codon sequences sampled from populations with recombination, migration and growth. Results: We introduce a new coalescent program, called Recodon, which is able to simulate samples of coding DNA sequences under complex scenarios in which several evolutionary forces can interact simultaneously (namely, recombination, migration and demography). The basic codon model implemented is an extension to the general time-reversible model of nucleotide substitution with a proportion of invariable sites and among-site rate variation. In addition, the program implements non-reversible processes and mixtures of different codon models. Conclusion: Recodon is a flexible tool for the simulation of coding DNA sequences under realistic evolutionary models. These simulations can be used to build parameter distributions for testing evolutionary hypotheses using experimental data. Recodon is written in C, can run in parallel, and is freely available from http://darwin.uvigo.es/. © 2007 Arenas and Posada; licensee BioMed Central Ltd." @Article{ArenasPosada2007,       AUTHOR = {Arenas, Miguel and Posada, David},       TITLE = {Recodon: Coalescent simulation of coding DNA sequences with recombination, migration and demography},       YEAR = {2008},       JOURNAL = {BMCB},       VOLUME = {8},       NUMBER = {458},       URL = {http://dx.doi.org/10.1186/1471-2105-8-458},       NOTE = {http://dx.doi.org/10.1186/1471-2105-8-458},       ANNOTE = {BIBUPDATE : 20081020},       KEYWORDS = {coalescent, generation, Program Recodon, software} } 168 Guohua Jin, Luay Nakhleh, Sagi Snir and Tamir Tuller. Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-time Heuristic. In TCBB, Vol. 6(3):495-505, 2009. Keywords: explicit network, heuristic, parsimony, phylogenetic network, phylogeny, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/tcbb-MP.pdf.         @Article{JNST2009,       AUTHOR = {Jin, Guohua and Nakhleh, Luay and Snir, Sagi and Tuller, Tamir},       TITLE = {Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-time Heuristic},       YEAR = {2009},       JOURNAL = {TCBB},       VOLUME = {6},       NUMBER = {3},       PAGES = {495-505},       URL = {http://dx.doi.org/10.1109/TCBB.2008.119},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/tcbb-MP.pdf},       ANNOTE = {BIBUPDATE : 20081028},       KEYWORDS = {explicit network, heuristic, parsimony, phylogenetic network, phylogeny, reconstruction} } 169 Alain Guénoche. Graphical Representation of a Boolean Array. In Computers and the Humanities, Vol. 20(4):277-281, 1986. Keywords: from splits, median network, reconstruction. Note: http://dx.doi.org/10.1007/BF02400118.         Toggle abstract "In this paper, we represent a boolean array of data with a median connected graph. Vertices are the different lines of the array plus virtual monomials, and an edge links two vertices that are different for only one variable. We describe an algorithm to compute this graph, that is an exact representation of the symmetrical difference distance between lines, and we show an application to Bronze age pins. © 1986 Paradigm Press, Inc." @Article{Guenoche1986,       AUTHOR = {Gu{\~A}�noche, Alain},       TITLE = {Graphical Representation of a Boolean Array},       YEAR = {1986},       JOURNAL = {Computers and the Humanities},       VOLUME = {20},       NUMBER = {4},       PAGES = {277-281},       URL = {http://dx.doi.org/10.1007/BF02400118},       NOTE = {http://dx.doi.org/10.1007/BF02400118},       KEYWORDS = {from splits, median network, reconstruction} } 170 Galina Glazko, Vladimir Makarenkov, Jing Liu and Arcady Mushegian. Evolutionary history of bacteriophages with double-stranded DNA genomes. In Biology Direct, Vol. 2(36), 2007. Keywords: explicit network, from sequences, phylogenetic network, phylogeny, Program T REX. Note: http://dx.doi.org/10.1186/1745-6150-2-36.         Toggle abstract "Background: Reconstruction of evolutionary history of bacteriophages is a difficult problem because of fast sequence drift and lack of omnipresent genes in phage genomes. Moreover, losses and recombinational exchanges of genes are so pervasive in phages that the plausibility of phylogenetic inference in phage kingdom has been questioned. Results: We compiled the profiles of presence and absence of 803 orthologous genes in 158 completely sequenced phages with double-stranded DNA genomes and used these gene content vectors to infer the evolutionary history of phages. There were 18 well-supported clades, mostly corresponding to accepted genera, but in some cases appearing to define new taxonomic groups. Conflicts between this phylogeny and trees constructed from sequence alignments of phage proteins were exploited to infer 294 specific acts of intergenome gene transfer. Conclusion: A notoriously reticulate evolutionary history of fast-evolving phages can be reconstructed in considerable detail by quantitative comparative genomics. © 2007 Glazko et al; licensee BioMed Central Ltd." @Article{GMLM2007,       AUTHOR = {Glazko, Galina and Makarenkov, Vladimir and Liu, Jing and Mushegian, Arcady},       TITLE = {Evolutionary history of bacteriophages with double-stranded DNA genomes},       YEAR = {2007},       JOURNAL = {Biology Direct},       VOLUME = {2},       NUMBER = {36},       URL = {http://dx.doi.org/10.1186/1745-6150-2-36},       NOTE = {http://dx.doi.org/10.1186/1745-6150-2-36},       ANNOTE = {BIBUPDATE : 20081110},       KEYWORDS = {explicit network, from sequences, phylogenetic network, phylogeny, Program T REX} } 171 Roderic D.M. Page and Michael A. Charleston. Trees within trees: phylogeny and historical associations. In TEE, Vol. 13(9):356-359, 1998. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, reconstruction, survey. Note: http://taxonomy.zoology.gla.ac.uk/rod/papers/tree.pdf.         @Article{PageCharleston1998,       AUTHOR = {Page, Roderic D.M. and Charleston, Michael A.},       TITLE = {Trees within trees: phylogeny and historical associations},       YEAR = {1998},       JOURNAL = {TEE},       VOLUME = {13},       NUMBER = {9},       PAGES = {356-359},       URL = {http://dx.doi.org/10.1016/s0169-5347(98)01438-4},       NOTE = {http://taxonomy.zoology.gla.ac.uk/rod/papers/tree.pdf},       ANNOTE = {BIBUPDATE : 20081127},       KEYWORDS = {duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, reconstruction, survey} } 172 Cuong Than, Derek Ruths, Hideki Innan and Luay Nakhleh. Confounding Factors in HGT Detection: Statistical Error, Coalescent Effects, and Multiple Solutions. In JCB, Vol. 14(4):517-535, 2007. Keywords: counting, explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, Program LatTrans, Program PhyloNet. Note: http://www.cs.rice.edu/~nakhleh/Papers/recombcg06-jcb.pdf.         @Article{TRIN2007,       AUTHOR = {Than, Cuong and Ruths, Derek and Innan, Hideki and Nakhleh, Luay},       TITLE = {Confounding Factors in HGT Detection: Statistical Error, Coalescent Effects, and Multiple Solutions},       YEAR = {2007},       JOURNAL = {JCB},       VOLUME = {14},       NUMBER = {4},       PAGES = {517-535},       URL = {http://dx.doi.org/10.1089/cmb.2007.A010},       NOTE = {http://www.cs.rice.edu/~nakhleh/Papers/recombcg06-jcb.pdf},       ANNOTE = {BIBUPDATE : 20081127},       KEYWORDS = {counting, explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, Program LatTrans, Program PhyloNet} } 173 Vassily A. Lyubetsky and Vladimir V. V´yugin. Methods of horizontal gene transfer determination using phylogenetic data. In In Silico Biology, Vol. 3(1-2):17-31, 2003. Note: http://www.bioinfo.de/isb/2003030003/.         @Article{LyubetskyVyugin2003,       AUTHOR = {Lyubetsky, Vassily A. and V{\^A}�yugin, Vladimir V.},       TITLE = {Methods of horizontal gene transfer determination using phylogenetic data},       YEAR = {2003},       JOURNAL = {In Silico Biology},       VOLUME = {3},       NUMBER = {1-2},       PAGES = {17-31},       NOTE = {http://www.bioinfo.de/isb/2003030003/},       ANNOTE = {BIBUPDATE : 20081127} } 174 Bin Ma, Lusheng Wang and Ming Li. Fixed topology alignment with recombination. In DAM, Vol. 104:281-300, 2000. Keywords: approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.7759.         Toggle abstract "Background: Reticulate events play an important role in determining evolutionary relationships. The problem of computing the minimum number of such events to explain discordance between two phylogenetic trees is a hard computational problem. Even for binary trees, exact solvers struggle to solve instances with reticulation number larger than 40-50.Results: Here we present CycleKiller and NonbinaryCycleKiller, the first methods to produce solutions verifiably close to optimality for instances with hundreds or even thousands of reticulations.Conclusions: Using simulations, we demonstrate that these algorithms run quickly for large and difficult instances, producing solutions that are very close to optimality. As a spin-off from our simulations we also present TerminusEst, which is the fastest exact method currently available that can handle nonbinary trees: this is used to measure the accuracy of the NonbinaryCycleKiller algorithm. All three methods are based on extensions of previous theoretical work (SIDMA 26(4):1635-1656, TCBB 10(1):18-25, SIDMA 28(1):49-66) and are publicly available. We also apply our methods to real data. © 2014 van Iersel et al.; licensee BioMed Central Ltd." @Article{MWL2000,       AUTHOR = {Ma, Bin and Wang, Lusheng and Li, Ming},       TITLE = {Fixed topology alignment with recombination},       YEAR = {2000},       JOURNAL = {DAM},       VOLUME = {104},       PAGES = {281-300},       URL = {http://dx.doi.org/10.1186/1471-2105-15-127},       NOTE = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.7759},       ANNOTE = {BIBUPDATE : 20081225},       KEYWORDS = {approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination} } 175 Ran Libeskind-Hadas and Michael A. Charleston. On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem. In JCB, Vol. 16(1):105-117, 2009. Keywords: cophylogeny, heuristic, NP complete, parsimony, phylogenetic network, reconstruction. Note: http://dx.doi.org/10.1089/cmb.2008.0084.         Toggle abstract "The cophylogeny reconstruction problem is that of finding minimal cost explanations of differences between evolutionary histories of ecologically linked groups of biological organisms. We present a proof that shows that the general problem of reconciling evolutionary histories is NP-complete and provide a sharp boundary where this intractability begins. We also show that a related problem, that of finding Pareto optimal solutions, is NP-hard. As a byproduct of our results, we give a framework by which meta-heuristics can be applied to find good solutions to this problem. © Mary Ann Liebert, Inc. 2009." @Article{LiebeskindCharleston2009,       AUTHOR = {Libeskind-Hadas, Ran and Charleston, Michael A.},       TITLE = {On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem},       YEAR = {2009},       JOURNAL = {JCB},       VOLUME = {16},       NUMBER = {1},       PAGES = {105-117},       URL = {http://dx.doi.org/10.1089/cmb.2008.0084},       NOTE = {http://dx.doi.org/10.1089/cmb.2008.0084},       ANNOTE = {BIBUPDATE : 20090105},       KEYWORDS = {cophylogeny, heuristic, NP complete, parsimony, phylogenetic network, reconstruction} } 176 Johannes Fischer and Daniel H. Huson. New Common Ancestor Problems in Trees and Directed Acyclic Graphs. In IPL, Vol. 110(8-9):331-335, 2010. Keywords: explicit network, phylogenetic network, polynomial. Note: http://www-ab.informatik.uni-tuebingen.de/people/fischer/lsa.pdf.         Toggle abstract "We derive a new generalization of lowest common ancestors (LCAs) in dags, called the lowest single common ancestor (LSCA). We show how to preprocess a static dag in linear time such that subsequent LSCA-queries can be answered in constant time. The size is linear in the number of nodes. We also consider a "fuzzy" variant of LSCA that allows to compute a node that is only an LSCA of a given percentage of the query nodes. The space and construction time of our scheme for fuzzy LSCAs is linear, whereas the query time has a sub-logarithmic slow-down. This "fuzzy" algorithm is also applicable to LCAs in trees, with the same complexities. © 2010 Elsevier B.V. All rights reserved." @Article{FischerHuson2010,       AUTHOR = {Fischer, Johannes and Huson, Daniel H.},       TITLE = {New Common Ancestor Problems in Trees and Directed Acyclic Graphs},       YEAR = {2010},       JOURNAL = {IPL},       VOLUME = {110},       NUMBER = {8-9},       PAGES = {331-335},       URL = {http://dx.doi.org/10.1016/j.ipl.2010.02.014},       NOTE = {http://www-ab.informatik.uni-tuebingen.de/people/fischer/lsa.pdf},       KEYWORDS = {explicit network, phylogenetic network, polynomial} } 177 Stephen J. Willson. Regular Networks Can Be Uniquely Constructed from Their Trees. In TCBB, Vol. 8(3):785-796, 2010. Keywords: explicit network, from rooted trees, phylogenetic network, phylogeny, reconstruction, regular network. Note: http://www.public.iastate.edu/~swillson/RegularNetsFromTrees5.pdf.         Toggle abstract "A rooted acyclic digraph N with labeled leaves displays a tree T when there exists a way to select a unique parent of each hybrid vertex resulting in the tree T. Let Tr(N) denote the set of all trees displayed by the network N. In general, there may be many other networks M, such that Tr(M) = Tr(N). A network is regular if it is isomorphic with its cover digraph. If N is regular and D is a collection of trees displayed by N, this paper studies some procedures to try to reconstruct N given D. If the input is D=Tr(N), one procedure is described, which will reconstruct N. Hence, if N and M are regular networks and Tr(N) = Tr(M), it follows that N = M, proving that a regular network is uniquely determined by its displayed trees. If D is a (usually very much smaller) collection of displayed trees that satisfies certain hypotheses, modifications of the procedure will still reconstruct N given D. © 2011 IEEE." @Article{Willson2010,       AUTHOR = {Willson, Stephen J.},       TITLE = {Regular Networks Can Be Uniquely Constructed from Their Trees},       YEAR = {2010},       JOURNAL = {TCBB},       VOLUME = {8},       NUMBER = {3},       PAGES = {785-796},       URL = {http://dx.doi.org/10.1109/TCBB.2010.69},       NOTE = {http://www.public.iastate.edu/~swillson/RegularNetsFromTrees5.pdf},       KEYWORDS = {explicit network, from rooted trees, phylogenetic network, phylogeny, reconstruction, regular network} } 178 Martin Lott, Andreas Spillner, Katharina Huber and Vincent Moulton. PADRE: A Package for Analyzing and Displaying Reticulate Evolution. In BIO, Vol. 25(9):1199-1200, 2009. Keywords: duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction, software. Note: http://dx.doi.org/10.1093/bioinformatics/btp133.         Toggle abstract "Recent advances in gene sequencing for polyploid species, coupled with standard phylogenetic tree reconstruction, leads to gene trees in which the same species can label several leaves. Such multi-labeled trees are then used to reconstruct the evolutionary history of the polyploid species in question. However, this reconstruction process requires new techniques that are not available in current phylogenetic software packages. Here, we describe the software package PADRE (Package for Analyzing and Displaying Reticulate Evolution) that implements such techniques, allowing the reconstruction of complex evolutionary histories for polyploids in the form of phylogenetic networks. © The Author 2009. Published by Oxford University Press. All rights reserved." @Article{LSHM2009,       AUTHOR = {Lott, Martin and Spillner, Andreas and Huber, Katharina and Moulton, Vincent},       TITLE = {PADRE: A Package for Analyzing and Displaying Reticulate Evolution},       YEAR = {2009},       JOURNAL = {BIO},       VOLUME = {25},       NUMBER = {9},       PAGES = {1199-1200},       URL = {http://dx.doi.org/10.1093/bioinformatics/btp133},       NOTE = {http://dx.doi.org/10.1093/bioinformatics/btp133},       KEYWORDS = {duplication, explicit network, from multilabeled tree, phylogenetic network, phylogeny, Program PADRE, reconstruction, software} } 179 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. The comparison of tree-sibling time consistent phylogenetic networks is graph-isomorphism complete. In The Scientific World Journal, Vol. 2014(254279):1-6, 2014. Keywords: abstract network, distance between networks, from network, isomorphism, phylogenetic network, tree sibling network. Note: http://arxiv.org/abs/0902.4640.         Toggle abstract "Several polynomial time computable metrics on the class of semibinary tree-sibling time consistent phylogenetic networks are available in the literature; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinarity condition, then the problem becomes much harder. More precisely, we prove that the isomorphism problem for generic tree-sibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem. Since the latter is believed not to belong to P, the chances are that it is impossible to define a metric on the class of all tree-sibling time consistent phylogenetic networks that can be computed in polynomial time. © 2014 Gabriel Cardona et al." @Article{CLRV2014,       AUTHOR = {Cardona, Gabriel and Llabr{\~A}�s, Merc{\~A}� and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {The comparison of tree-sibling time consistent phylogenetic networks is graph-isomorphism complete},       YEAR = {2014},       JOURNAL = {The Scientific World Journal},       VOLUME = {2014},       NUMBER = {254279},       PAGES = {1-6},       URL = {http://dx.doi.org/10.1155/2014/254279},       NOTE = {http://arxiv.org/abs/0902.4640},       KEYWORDS = {abstract network, distance between networks, from network, isomorphism, phylogenetic network, tree sibling network} } 180 Peter J. Humphries and Charles Semple. Note on the hybridization number and subtree distance in phylogenetics. In Applied Mathematics Letters, Vol. 22(4):611-615, 2009. Keywords: explicit network, minimum number, phylogenetic network, phylogeny, SPR distance. Note: http://www.math.canterbury.ac.nz/~c.semple/papers/HS08.pdf.         @Article{HumphriesSemple2009,       AUTHOR = {Humphries, Peter J. and Semple, Charles},       TITLE = {Note on the hybridization number and subtree distance in phylogenetics},       YEAR = {2009},       JOURNAL = {Applied Mathematics Letters},       VOLUME = {22},       NUMBER = {4},       PAGES = {611-615},       URL = {http://dx.doi.org/10.1016/j.aml.2008.08.018},       NOTE = {http://www.math.canterbury.ac.nz/~c.semple/papers/HS08.pdf},       KEYWORDS = {explicit network, minimum number, phylogenetic network, phylogeny, SPR distance} } 181 Laxmi Parida, Asif Javed, Marta Melé, Francesc Calafell, Jaume Bertranpetit and Genographic Consortium. Minimizing recombinations in consensus networks for phylogeographic studies. In BMCB, Vol. 10(Suppl 1):S72, 2009. Note: Selected papers from the Seventh Asia-Pacific Bioinformatics Conference (APBC 2009), http://dx.doi.org/10.1186/1471-2105-10-S1-S72.         Toggle abstract "Background: We address the problem of studying recombinational variations in (human) populations. In this paper, our focus is on one computational aspect of the general task: Given two networks G1 and G2, with both mutation and recombination events, defined on overlapping sets of extant units the objective is to compute a consensus network G3 with minimum number of additional recombinations. We describe a polynomial time algorithm with a guarantee that the number of computed new recombination events is within = sz(G1, G2) (function sz is a well-behaved function of the sizes and topologies of G1 and G2) of the optimal number of recombinations. To date, this is the best known result for a network consensus problem. Results: Although the network consensus problem can be applied to a variety of domains, here we focus on structure of human populations. With our preliminary analysis on a segment of the human Chromosome X data we are able to infer ancient recombinations, population-specific recombinations and more, which also support the widely accepted 'Out of Africa' model. These results have been verified independently using traditional manual procedures. To the best of our knowledge, this is the first recombinations-based characterization of human populations. Conclusion: We show that our mathematical model identifies recombination spots in the individual haplotypes; the aggregate of these spots over a set of haplotypes defines a recombinational landscape that has enough signal to detect continental as well as population divide based on a short segment of Chromosome X. In particular, we are able to infer ancient recombinations, population-specific recombinations and more, which also support the widely accepted 'Out of Africa' model. The agreement with mutation-based analysis can be viewed as an indirect validation of our results and the model. Since the model in principle gives us more information embedded in the networks, in our future work, we plan to investigate more non-traditional questions via these structures computed by our methodology. © 2009 Parida et al; licensee BioMed Central Ltd." @Article{PJMCBG2009,       AUTHOR = {Parida, Laxmi and Javed, Asif and Mel{\~A}�, Marta and Calafell, Francesc and Bertranpetit, Jaume and Consortium, Genographic},       TITLE = {Minimizing recombinations in consensus networks for phylogeographic studies},       YEAR = {2009},       JOURNAL = {BMCB},       VOLUME = {10},       NUMBER = {Suppl 1},       PAGES = {S72},       URL = {http://dx.doi.org/10.1186/1471-2105-10-S1-S72},       NOTE = {Selected papers from the Seventh Asia-Pacific Bioinformatics Conference (APBC 2009), http://dx.doi.org/10.1186/1471-2105-10-S1-S72} } 182 Francesc Rosselló and Gabriel Valiente. All that Glisters is not Galled. In MBIO, Vol. 221(1):54-59, 2009. Keywords: galled tree, phylogenetic network, phylogeny. Note: http://arxiv.org/abs/0904.2448.         Toggle abstract "Galled trees, evolutionary networks with isolated reticulation cycles, have appeared under several slightly different definitions in the literature. In this paper, we establish the actual relationships between the main four such alternative definitions: namely, the original galled trees, level-1 networks, nested networks with nesting depth 1, and evolutionary networks with arc-disjoint reticulation cycles. © 2009 Elsevier Inc. All rights reserved." @Article{RosselloValiente2009,       AUTHOR = {Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {All that Glisters is not Galled},       YEAR = {2009},       JOURNAL = {MBIO},       VOLUME = {221},       NUMBER = {1},       PAGES = {54-59},       URL = {http://dx.doi.org/10.1016/j.mbs.2009.06.007},       NOTE = {http://arxiv.org/abs/0904.2448},       KEYWORDS = {galled tree, phylogenetic network, phylogeny} } 183 Philippe Gambette and Katharina Huber. On Encodings of Phylogenetic Networks of Bounded Level. In JOMB, Vol. 65(1):157-180, 2012. Keywords: characterization, explicit network, from clusters, from rooted trees, from triplets, galled tree, identifiability, level k phylogenetic network, phylogenetic network, uniqueness, weak hierarchy. Note: http://hal.archives-ouvertes.fr/hal-00609130/en/.         Toggle abstract "Phylogenetic networks have now joined phylogenetic trees in the center of phylogenetics research. Like phylogenetic trees, such networks canonically induce collections of phylogenetic trees, clusters, and triplets, respectively. Thus it is not surprising that many network approaches aim to reconstruct a phylogenetic network from such collections. Related to the well-studied perfect phylogeny problem, the following question is of fundamental importance in this context: When does one of the above collections encode (i. e. uniquely describe) the network that induces it? For the large class of level-1 (phylogenetic) networks we characterize those level-1 networks for which an encoding in terms of one (or equivalently all) of the above collections exists. In addition, we show that three known distance measures for comparing phylogenetic networks are in fact metrics on the resulting subclass and give the diameter for two of them. Finally, we investigate the related concept of indistinguishability and also show that many properties enjoyed by level-1 networks are not satisfied by networks of higher level. © 2011 Springer-Verlag." @Article{GambetteHuber2012,       AUTHOR = {Gambette, Philippe and Huber, Katharina},       TITLE = {On Encodings of Phylogenetic Networks of Bounded Level},       YEAR = {2012},       JOURNAL = {JOMB},       VOLUME = {65},       NUMBER = {1},       PAGES = {157-180},       URL = {http://dx.doi.org/10.1007/s00285-011-0456-y},       NOTE = {http://hal.archives-ouvertes.fr/hal-00609130/en/},       KEYWORDS = {characterization, explicit network, from clusters, from rooted trees, from triplets, galled tree, identifiability, level k phylogenetic network, phylogenetic network, uniqueness, weak hierarchy} } 184 Gabriel Cardona, Mercè Llabrés, Francesc Rosselló and Gabriel Valiente. Comparison of Galled Trees. In TCBB, Vol. 8(2):410-427, 2011. Note: http://arxiv.org/abs/0906.1166.         Toggle abstract "Galled trees, directed acyclic graphs that model evolutionary histories with isolated hybridization events, have become very popular due to both their biological significance and the existence of polynomial-time algorithms for their reconstruction. In this paper, we establish to which extent several distance measures for the comparison of evolutionary networks are metrics for galled trees, and hence, when they can be safely used to evaluate galled tree reconstruction methods. © 2011 IEEE." @Article{CLRV2011,       AUTHOR = {Cardona, Gabriel and Llabr{\~A}�s, Merc{\~A}� and Rossell{\~A}�, Francesc and Valiente, Gabriel},       TITLE = {Comparison of Galled Trees},       YEAR = {2011},       JOURNAL = {TCBB},       VOLUME = {8},       NUMBER = {2},       PAGES = {410-427},       URL = {http://dx.doi.org/10.1109/TCBB.2010.60},       NOTE = {http://arxiv.org/abs/0906.1166} } 185 Sarah C. Ayling and Terence A. Brown. Novel methodology for construction and pruning of quasi-median networks. In BMCB, Vol. 9:115, 2009. Keywords: abstract network, from sequences, median network, phylogenetic network, phylogeny, quasi-median network, reconstruction. Note: http://dx.doi.org/10.1186/1471-2105-9-115.         Toggle abstract "BACKGROUND: Visualising the evolutionary history of a set of sequences is a challenge for molecular phylogenetics. One approach is to use undirected graphs, such as median networks, to visualise phylogenies where reticulate relationships such as recombination or homoplasy are displayed as cycles. Median networks contain binary representations of sequences as nodes, with edges connecting those sequences differing at one character; hypothetical ancestral nodes are invoked to generate a connected network which contains all most parsimonious trees. Quasi-median networks are a generalisation of median networks which are not restricted to binary data, although phylogenetic information contained within the multistate positions can be lost during the preprocessing of data. Where the history of a set of samples contain frequent homoplasies or recombination events quasi-median networks will have a complex topology. Graph reduction or pruning methods have been used to reduce network complexity but some of these methods are inapplicable to datasets in which recombination has occurred and others are procedurally complex and/or result in disconnected networks. RESULTS: We address the problems inherent in construction and reduction of quasi-median networks. We describe a novel method of generating quasi-median networks that uses all characters, both binary and multistate, without imposing an arbitrary ordering of the multistate partitions. We also describe a pruning mechanism which maintains at least one shortest path between observed sequences, displaying the underlying relations between all pairs of sequences while maintaining a connected graph. CONCLUSION: Application of this approach to 5S rDNA sequence data from sea beet produced a pruned network within which genetic isolation between populations by distance was evident, demonstrating the value of this approach for exploration of evolutionary relationships." @Article{AylingBrown2009,       AUTHOR = {Ayling, Sarah C. and Brown, Terence A.},       TITLE = {Novel methodology for construction and pruning of quasi-median networks},       YEAR = {2009},       JOURNAL = {BMCB},       VOLUME = {9},       PAGES = {115},       URL = {http://dx.doi.org/10.1186/1471-2105-9-115},       NOTE = {http://dx.doi.org/10.1186/1471-2105-9-115},       KEYWORDS = {abstract network, from sequences, median network, phylogenetic network, phylogeny, quasi-median network, reconstruction} } 186 Hadas Birin, Zohar Gal-Or, Isaac Elias and Tamir Tuller. Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion. In BIO, Vol. 24(6):826-832, 2008. Note: http://dx.doi.org/10.1093/bioinformatics/btn024.         Toggle abstract "Motivation: The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements and horizontal transfer of genetic materials (HGTS). Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. These facts encourage developing methods for inferring phylogenetic networks that do not require aligned sequences as input. Results: In this work, we present the first computational approach which deals with both genome rearrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution. We investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as four biological datasets. © The Author 2008. Published by Oxford University Press. All rights reserved." @Article{BGET2008,       AUTHOR = {Birin, Hadas and Gal-Or, Zohar and Elias, Isaac and Tuller, Tamir},       TITLE = {Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion},       YEAR = {2008},       JOURNAL = {BIO},       VOLUME = {24},       NUMBER = {6},       PAGES = {826-832},       URL = {http://dx.doi.org/10.1093/bioinformatics/btn024},       NOTE = {http://dx.doi.org/10.1093/bioinformatics/btn024} } 187 Frederick A. Matsen. ConstNJ: an algorithm to reconstruct sets of phylogenetic trees satisfying pairwise topological constraints. In JCB, Vol. 17(6):799-818, 2010. Keywords: from distances, Program constNJ, reconstruction. Note: http://arxiv.org/abs/0901.1598v2.         Toggle abstract "This article introduces constNJ (constrained neighbor-joining), an algorithm for phylogenetic reconstruction of sets of trees with constrained pairwise rooted subtree-prune-regraft (rSPR) distance. We are motivated by the problem of constructing sets of trees that must fit into a recombination, hybridization, or similar network. Rather than first finding a set of trees that are optimal according to a phylogenetic criterion (e.g., likelihood or parsimony) and then attempting to fit them into a network, constNJ estimates the trees while enforcing specified rSPR distance constraints. The primary input for constNJ is a collection of distance matrices derived from sequence blocks which are assumed to have evolved in a tree-like manner, such as blocks of an alignment which do not contain any recombination breakpoints. The other input is a set of rSPR constraint inequalities for any set of pairs of trees. constNJ is consistent and a strict generalization of the neighbor-joining algorithm; it uses the new notion of maximum agreement partitions (MAPs) to assure that the resulting trees satisfy the given rSPR distance constraints. Copyright 2010, Mary Ann Liebert, Inc." @Article{Matsen2010,       AUTHOR = {Matsen, Frederick A.},       TITLE = {ConstNJ: an algorithm to reconstruct sets of phylogenetic trees satisfying pairwise topological constraints},       YEAR = {2010},       JOURNAL = {JCB},       VOLUME = {17},       NUMBER = {6},       PAGES = {799-818},       URL = {http://dx.doi.org/10.1089/cmb.2009.0201},       NOTE = {http://arxiv.org/abs/0901.1598v2},       KEYWORDS = {from distances, Program constNJ, reconstruction} } 188 Stefan Grünewald, Jacobus Koolen and Woo-Sun Lee. Quartets in maximal weakly compatible split systems. In Applied Mathematics Letters, Vol. 22(6):1604-1608, 2009. Note: http://dx.doi.org/10.1016/j.aml.2009.05.006.         Toggle abstract "Weakly compatible split systems are a generalization of unrooted evolutionary trees and are commonly used to display reticulate evolution or ambiguity in biological data. They are collections of bipartitions of a finite set X of taxa (e.g. species) with the property that, for every four taxa, at least one of the three bipartitions into two pairs (quartets) is not induced by any of the X-splits. We characterize all split systems where exactly two quartets from every quadruple are induced by some split. On the other hand, we construct maximal weakly compatible split systems where the number of induced quartets per quadruple tends to 0 with the number of taxa going to infinity. © 2009." @Article{GKL2009,       AUTHOR = {Gr{\~A}�newald, Stefan and Koolen, Jacobus and Lee, Woo-Sun},       TITLE = {Quartets in maximal weakly compatible split systems},       YEAR = {2009},       JOURNAL = {Applied Mathematics Letters},       VOLUME = {22},       NUMBER = {6},       PAGES = {1604-1608},       URL = {http://dx.doi.org/10.1016/j.aml.2009.05.006},       NOTE = {http://dx.doi.org/10.1016/j.aml.2009.05.006} } 189 Stephen J. Willson. Properties of normal phylogenetic networks. In BMB, Vol. 72(2):340-358, 2010. Keywords: normal network, phylogenetic network, phylogeny, regular network. Note: http://www.public.iastate.edu/~swillson/RestrictionsOnNetworkspap9.pdf, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/willson/.         Toggle abstract "A phylogenetic network is a rooted acyclic digraph with vertices corresponding to taxa. Let X denote a set of vertices containing the root, the leaves, and all vertices of outdegree 1. Regard X as the set of vertices on which measurements such as DNA can be made. A vertex is called normal if it has one parent, and hybrid if it has more than one parent. The network is called normal if it has no redundant arcs and also from every vertex there is a directed path to a member of X such that all vertices after the first are normal. This paper studies properties of normal networks. Under a simple model of inheritance that allows homoplasies only at hybrid vertices, there is essentially unique determination of the genomes at all vertices by the genomes at members of X if and only if the network is normal. This model is a limiting case of more standard models of inheritance when the substitution rate is sufficiently low. Various mathematical properties of normal networks are described. These properties include that the number of vertices grows at most quadratically with the number of leaves and that the number of hybrid vertices grows at most linearly with the number of leaves. © 2009 Society for Mathematical Biology." @Article{Willson2010b,       AUTHOR = {Willson, Stephen J.},       TITLE = {Properties of normal phylogenetic networks},       YEAR = {2010},       JOURNAL = {BMB},       VOLUME = {72},       NUMBER = {2},       PAGES = {340-358},       URL = {http://dx.doi.org/10.1007/s11538-009-9449-z},       NOTE = {http://www.public.iastate.edu/~swillson/RestrictionsOnNetworkspap9.pdf, slides available at http://www.newton.cam.ac.uk/webseminars/pg+ws/2007/plg/plgw01/0904/willson/},       KEYWORDS = {normal network, phylogenetic network, phylogeny, regular network} } 190 Katharina Huber, Leo van Iersel, Steven Kelk and Radoslaw Suchecki. A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks. In TCBB, Vol. 8(3):607-620, 2011. Keywords: explicit network, from triplets, galled tree, generation, heuristic, phylogenetic network, phylogeny, Program LEV1ATHAN, Program Lev1Generator, reconstruction, software. Note: http://arxiv.org/abs/0910.4067.         Toggle abstract "Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 phylogenetic networks-a type of network slightly more general than a phylogenetic tree-from triplets. Our algorithm has been made publicly available as the program Lev1athan. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponential-time exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, Lev1athan runs in polynomial time and always constructs a level-1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense