| |
Hans-Jürgen Bandelt and
Arne Dür. Translating DNA data tables into quasi-median networks for parsimony analysis and error detection. In MPE, Vol. 42(1):256-271, 2007.
Keywords: abstract network, from sequences, parsimony, phylogenetic network, phylogeny, quasi-median network, reconstruction.
Note: http://dx.doi.org/10.1016/j.ympev.2006.07.013.
Toggle abstract
"Every DNA data table can be turned into a quasi-median network that faithfully represents the data. We show that for (weighted) condensed data tables the associated network harbors all most parsimonious reconstructions for any tree that connects the sampled haplotypes. Structural features of this network can be computed directly from the data table. The key principle repeatedly used is that the quasi-median network is uniquely determined by the sub-tables for pairs of characters. The translation of a table into a network enhances the understanding of the properties of the data in regard to homoplasy and potential artifacts. The total number of nodes of such a network measures the complexity of the data. In particular, networks that display the results of filter analyses by which hotspot mutations are removed help to detect data idiosyncrasies and thus pinpoint sequencing problems. A pertinent example drawn from human mtDNA illustrates these points. © 2006 Elsevier Inc. All rights reserved."
|
|
| |
|
| |
|
| |
   
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."
|
|
| |
Nicolas Galtier. A model of horizontal gene transfer and the bacterial phylogeny problem. In Systematic Biology, Vol. 56(4):633-642, 2007.
Keywords: explicit network, generation, lateral gene transfer, phylogenetic network, phylogeny, Program HGT_simul, software, statistical model.
Note: http://dx.doi.org/10.1080/10635150701546231.
Toggle abstract
"How much horizontal gene transfer (HGT) between species influences bacterial phylogenomics is a controversial issue. This debate, however, lacks any quantitative assessment of the impact of HGT on phylogenies and of the ability of tree-building methods to cope with such events. I introduce a Markov model of genome evolution with HGT, accounting for the constraints on time-an HGT event can only occur between concomitantly living species. This model is used to simulate multigene sequence data sets with or without HGT. The consequences of HGT on phylogenomic inference are analyzed and compared to other well-known phylogenetic artefacts. It is found that supertree methods are quite robust to HGT, keeping high levels of performance even when gene trees are largely incongruent with each other. Gene tree incongruence per se is not indicative of HGT. HGT, however, removes the (otherwise observed) positive relationship between sequence length and gene tree congruence to the estimated species tree. Surprisingly, when applied to a bacterial and a eukaryotic multigene data set, this criterion rejects the HGT hypothesis for the former, but not the latter data set. Copyright © Society of Systematic Biologists."
|
|
| |
 
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."
|
|
| |
|
| |
   
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.
|
|
| |
Pawel Górecki. Detection of horizontal gene transfer. PhD thesis, Warsaw University, Poland, 2006.
Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction.
|
|
| |
|
| |
Guillaume Bourque and
Louxin Zhang. Models and Methods in Comparative Genomics. In
Chau-Wen Tseng editor, Advances in Computers, Special Volume: Computational Biology, Vol. 68, Elsevier, 2006.
Keywords: from distances, from rooted trees, from sequences, galled tree, phylogenetic network, phylogeny, survey.
Note: http://www.math.nus.edu.sg/~matzlx/papers/CompGen_ZLX.pdf.
|
|
| |
|
| |
  
Vladimir Makarenkov,
Dmytro Kevorkov and
Pierre Legendre. Phylogenetic Network Construction Approaches. In Applied Mycology and Biotechnology, Vol. 6:61-97, 2006.
Keywords: from distances, hybridization, lateral gene transfer, median network, NeighborNet, netting, Program Arlequin, Program Network, Program Pyramids, Program Reticlad, Program SplitsTree, Program T REX, Program TCS, Program WeakHierarchies, pyramid, reticulogram, split, split decomposition, split network, survey, weak hierarchy.
Note: http://www.labunix.uqam.ca/~makarenv/makarenv/MKL_article.pdf.
|
|
| |
|
| |
|
| |
|
| |
   
Cuong Than,
Derek Ruths,
Hideki Innan and
Luay Nakhleh. Identifiability Issues in Phylogeny-Based Detection of Horizontal Gene Transfer. In Proceedings of the Fourth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'06), Vol. 4205:215-229 of LNCS, springer, 2006.
Keywords: 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-final.pdf.
|
|
| |
|
| |
|
| |
|
| |
|
| |
 
Mihaela Baroni and
Mike Steel. Accumulation Phylogenies. In ACOM, Vol. 10(1):19-30, 2006.
Keywords: abstract network, from clusters, from distances, phylogenetic network, phylogeny, polynomial, reconstruction, regular network.
Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1960.
Toggle abstract
"We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multi-labeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NP-hard. Furthermore, we show that the general minimization problem is NP-hard to approximate within a ratio of n 1-ε for any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomial-time approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O *(7 n ) time and O *(3 n ) space. © 2009 Springer-Verlag Berlin Heidelberg."
|
|
| |
  
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.
|
|
| |
 
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."
|
|
| |
 
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."
|
|
| |
|
| |
 
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."
|
|
| |
   
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."
|
|
| |
 
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."
|
|
| |
|
|
- forked on GitHub.