| |
 
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."
|
|
| |
Stephen J. Willson. CSD Homomorphisms Between Phylogenetic Networks. In TCBB, Vol. 9(4), 2012.
Keywords: explicit network, from network, from quartets, phylogenetic network.
Note: http://www.public.iastate.edu/~swillson/Relationships11IEEE.pdf, preliminary version entitled Relationships Among Phylogenetic Networks.
Toggle abstract
"Since Darwin, species trees have been used as a simplified description of the relationships which summarize the complicated network N of reality. Recent evidence of hybridization and lateral gene transfer, however, suggest that there are situations where trees are inadequate. Consequently it is important to determine properties that characterize networks closely related to N and possibly more complicated than trees but lacking the full complexity of N. A connected surjective digraph map (CSD) is a map f from one network N to another network M such that every arc is either collapsed to a single vertex or is taken to an arc, such that f is surjective, and such that the inverse image of a vertex is always connected. CSD maps are shown to behave well under composition. It is proved that if there is a CSD map from N to M, then there is a way to lift an undirected version of M into N, often with added resolution. A CSD map from N to M puts strong constraints on N. In general, it may be useful to study classes of networks such that, for any N, there exists a CSD map from N to some standard member of that class. © 2012 IEEE."
|
|
| |
  
Steven Kelk,
Celine Scornavacca and
Leo van Iersel. On the elusiveness of clusters. In TCBB, Vol. 9(2):517-534, 2012.
Keywords: explicit network, from clusters, from rooted trees, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, Program Clustistic, reconstruction, software.
Note: http://arxiv.org/abs/1103.1834.
|
|
| |
 
Celine Scornavacca,
Simone Linz and
Benjamin Albrecht. A fi rst step towards computing all hybridization networks for two rooted binary phylogenetic trees. In JCB, Vol. 19:1227-1242, 2012.
Keywords: agreement forest, explicit network, FPT, from rooted trees, phylogenetic network, phylogeny, Program Dendroscope, Program Hybroscale, reconstruction.
Note: http://arxiv.org/abs/1109.3268.
Toggle abstract
"Recently, considerable effort has been put into developing fast algorithms to reconstruct a rooted phylogenetic network that explains two rooted phylogenetic trees and has a minimum number of hybridization vertices. With the standard app1235roach to tackle this problem being combinatorial, the reconstructed network is rarely unique. From a biological point of view, it is therefore of importance to not only compute one network, but all possible networks. In this article, we make a first step toward approaching this goal by presenting the first algorithm-called allMAAFs-that calculates all maximum-acyclic-agreement forests for two rooted binary phylogenetic trees on the same set of taxa. © Copyright 2012, Mary Ann Liebert, Inc. 2012."
|
|
| |
 
Zhi-Zhong Chen and
Lusheng Wang. Algorithms for Reticulate Networks of Multiple Phylogenetic Trees. In TCBB, Vol. 9(2):372-384, 2012.
Keywords: explicit network, from rooted trees, minimum number, phylogenetic network, phylogeny, Program CMPT, Program MaafB, reconstruction, software.
Note: http://rnc.r.dendai.ac.jp/~chen/papers/rMaaf.pdf.
Toggle abstract
"A reticulate network N of multiple phylogenetic trees may have nodes with two or more parents (called reticulation nodes). There are two ways to define the reticulation number of N. One way is to define it as the number of reticulation nodes in N in this case, a reticulate network with the smallest reticulation number is called an optimal type-I reticulate network of the trees. The better way is to define it as the total number of parents of reticulation nodes in N minus the number of reticulation nodes in N ; in this case, a reticulate network with the smallest reticulation number is called an optimal type-II reticulate network of the trees. In this paper, we first present a fast fixed-parameter algorithm for constructing one or all optimal type-I reticulate networks of multiple phylogenetic trees. We then use the algorithm together with other ideas to obtain an algorithm for estimating a lower bound on the reticulation number of an optimal type-II reticulate network of the input trees. To our knowledge, these are the first fixed-parameter algorithms for the problems. We have implemented the algorithms in ANSI C, obtaining programs CMPT and MaafB. Our experimental data show that CMPT can construct optimal type-I reticulate networks rapidly and MaafB can compute better lower bounds for optimal type-II reticulate networks within shorter time than the previously best program PIRN designed by Wu. © 2006 IEEE."
|
|
| |
 
Benjamin Albrecht,
Celine Scornavacca,
Alberto Cenci and
Daniel H. Huson. Fast computation of minimum hybridization networks. In BIO, Vol. 28(2):191-197, 2012.
Keywords: explicit network, from rooted trees, minimum number, phylogenetic network, phylogeny, Program Dendroscope, Program Hybroscale, reconstruction.
Note: http://dx.doi.org/10.1093/bioinformatics/btr618.
Toggle abstract
"Motivation: Hybridization events in evolution may lead to incongruent gene trees. One approach to determining possible interspecific hybridization events is to compute a hybridization network that attempts to reconcile incongruent gene trees using a minimum number of hybridization events. Results: We describe how to compute a representative set of minimum hybridization networks for two given bifurcating input trees, using a parallel algorithm and provide a user-friendly implementation. A simulation study suggests that our program performs significantly better than existing software on biologically relevant data. Finally, we demonstrate the application of such methods in the context of the evolution of the Aegilops/Triticum genera. Availability and implementation: The algorithm is implemented in the program Dendroscope 3, which is freely available from www.dendroscope.org and runs on all three major operating systems. © The Author 2011. Published by Oxford University Press. All rights reserved."
|
|
| |
 
Steven Kelk,
Leo van Iersel,
Nela Lekic,
Simone Linz,
Celine Scornavacca and
Leen Stougie. Cycle killer... qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set. In SIDMA, Vol. 26(4):1635-1656, 2012.
Keywords: agreement forest, approximation, explicit network, from rooted trees, minimum number, phylogenetic network, phylogeny, Program CycleKiller, reconstruction.
Note: http://arxiv.org/abs/1112.5359, about the title.
Toggle abstract
"We show that the problem of computing the hybridization number of two rooted binary phylogenetic trees on the same set of taxa X has a constant factor polynomial-time approximation if and only if the problem of computing a minimum-size feedback vertex set in a directed graph (DFVS) has a constant factor polynomial-time approximation. The latter problem, which asks for a minimum number of vertices to be removed from a directed graph to transform it into a directed acyclic graph, is one of the problems in Karp's seminal 1972 list of 21 NP-complete problems. Despite considerable attention from the combinatorial optimization community, it remains to this day unknown whether a constant factor polynomial-time approximation exists for DFVS. Our result thus places the (in)approximability of hybridization number in a much broader complexity context, and as a consequence we obtain that it inherits inapproximability results from the problem Vertex Cover. On the positive side, we use results from the DFVS literature to give an O(log r log log r) approximation for the hybridization number where r is the correct value. Copyright © by SIAM."
|
|
| |
 
Philippe Gambette,
Vincent Berry and
Christophe Paul. Quartets and Unrooted Phylogenetic Networks. In JBCB, Vol. 10(4):1250004, 2012.
Keywords: abstract network, circular split system, explicit network, from quartets, level k phylogenetic network, orientation, phylogenetic network, phylogeny, polynomial, reconstruction, split, split network.
Note: http://hal.archives-ouvertes.fr/hal-00678046/en/.
Toggle abstract
"Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of level-k networks. In particular, we give an equivalence theorem between circular split systems and unrooted level-1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted level-k phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions. © 2012 Imperial College Press."
|
|
| |
  
Yun Yu,
James H. Degnan and
Luay Nakhleh. The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection. In PLoS Genetics, Vol. 8(4):e1002660, 2012.
Keywords: AIC, BIC, explicit network, hybridization, phylogenetic network, phylogeny, statistical model.
Note: http://dx.doi.org/10.1371/journal.pgen.1002660.
Toggle abstract
"Gene tree topologies have proven a powerful data source for various tasks, including species tree inference and species delimitation. Consequently, methods for computing probabilities of gene trees within species trees have been developed and widely used in probabilistic inference frameworks. All these methods assume an underlying multispecies coalescent model. However, when reticulate evolutionary events such as hybridization occur, these methods are inadequate, as they do not account for such events. Methods that account for both hybridization and deep coalescence in computing the probability of a gene tree topology currently exist for very limited cases. However, no such methods exist for general cases, owing primarily to the fact that it is currently unknown how to compute the probability of a gene tree topology within the branches of a phylogenetic network. Here we present a novel method for computing the probability of gene tree topologies on phylogenetic networks and demonstrate its application to the inference of hybridization in the presence of incomplete lineage sorting. We reanalyze a Saccharomyces species data set for which multiple analyses had converged on a species tree candidate. Using our method, though, we show that an evolutionary hypothesis involving hybridization in this group has better support than one of strict divergence. A similar reanalysis on a group of three Drosophila species shows that the data is consistent with hybridization. Further, using extensive simulation studies, we demonstrate the power of gene tree topologies at obtaining accurate estimates of branch lengths and hybridization probabilities of a given phylogenetic network. Finally, we discuss identifiability issues with detecting hybridization, particularly in cases that involve extinction or incomplete sampling of taxa. © 2012 Yu et al."
|
|
| |
Hyun Jung Park and
Luay Nakhleh. MURPAR: A fast heuristic for inferring parsimonious phylogenetic networks from multiple gene trees. In ISBRA12, Vol. 7292:213-224 of LNCS, springer, 2012.
Keywords: explicit network, from unrooted trees, heuristic, phylogenetic network, phylogeny, reconstruction, software.
Note: https://www.researchgate.net/profile/Hyun_Jung_Park2/publication/262318595_MURPAR_A_Fast_Heuristic_for_Inferring_Parsimonious_Phylogenetic_Networks_from_Multiple_Gene_Trees/links/54b7e7b50cf269d8cbf58cc4.pdf.
Toggle abstract
"Phylogenetic networks provide a graphical representation of evolutionary histories that involve non-treelike evolutionary events, such as horizontal gene transfer (HGT). One approach for inferring phylogenetic networks is based on reconciling gene trees, assuming all incongruence among the gene trees is due to HGT. Several mathematical results and algorithms, both exact and heuristic, have been introduced to construct and analyze phylogenetic networks. Here, we address the computational problem of inferring phylogenetic networks with minimum reticulations from a collection of gene trees. As this problem is known to be NP-hard even for a pair of gene trees, the problem at hand is very hard. In this paper, we present an efficient heuristic, MURPAR, for inferring a phylogenetic network from a collection of gene trees by using pairwise reconciliations of trees in the collection. Given the development of efficient and accurate methods for pairwise gene tree reconciliations, MURPAR inherits this efficiency and accuracy. Further, the method includes a formulation for combining pairwise reconciliations that is naturally amenable to an efficient integer linear programming (ILP) solution. We show that MURPAR produces more accurate results than other methods and is at least as fast, when run on synthetic and biological data. We believe that our method is especially important for rapidly obtaining estimates of genome-scale evolutionary histories that can be further refined by more detailed and compute-intensive methods. © 2012 Springer-Verlag."
|
|
| |
 
Pawel Górecki and
Jerzy Tiuryn. Inferring evolutionary scenarios in the duplication, loss and horizontal gene transfer model. In Logic and Program Semantics, Vol. 7230:83-105 of LNCS, springer, 2012.
Keywords: duplication, explicit network, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction.
Note: http://dx.doi.org/10.1007/978-3-642-29485-3_7.
Toggle abstract
"An H-tree is a formal model of evolutionary scenario. It can be used to represent any processes with gene duplication and loss, horizontal gene transfer (HGT) and speciation events. The model of H-trees, introduced in [26], is an extension of the duplication-loss model (DL-model). Similarly to its ancestor, it has a number of interesting mathematical and biological properties. It is, however, more computationally complex than the DL-model. In this paper, we primarily address the problem of inferring H-trees that are compatible with a given gene tree and a given phylogeny of species with HGTs. These results create a mathematical and computational foundation for a more general and practical problem of inferring HGTs from given gene and species trees with HGTs. We also demonstrate how our model can be used to support HGT hypotheses based on empirical data sets. © 2012 Springer-Verlag Berlin Heidelberg."
|
|
| |
  
Mukul S. Bansal,
Eric J. Alm and
Manolis Kellis. Efficient Algorithms for the Reconciliation Problem with Gene Duplication, Horizontal Transfer, and Loss. In ISMB12, Vol. 28(12):i283-i291 of BIO, 2012.
Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Angst, Program Mowgli, Program RANGER-DTL, reconstruction.
Note: http://dx.doi.org/10.1093/bioinformatics/bts225.
Toggle abstract
"Motivation: Gene family evolution is driven by evolutionary events such as speciation, gene duplication, horizontal gene transfer and gene loss, and inferring these events in the evolutionary history of a given gene family is a fundamental problem in comparative and evolutionary genomics with numerous important applications. Solving this problem requires the use of a reconciliation framework, where the input consists of a gene family phylogeny and the corresponding species phylogeny, and the goal is to reconcile the two by postulating speciation, gene duplication, horizontal gene transfer and gene loss events. This reconciliation problem is referred to as duplication-transfer-loss (DTL) reconciliation and has been extensively studied in the literature. Yet, even the fastest existing algorithms for DTL reconciliation are too slow for reconciling large gene families and for use in more sophisticated applications such as gene tree or species tree reconstruction.Results: We present two new algorithms for the DTL reconciliation problem that are dramatically faster than existing algorithms, both asymptotically and in practice. We also extend the standard DTL reconciliation model by considering distance-dependent transfer costs, which allow for more accurate reconciliation and give an efficient algorithm for DTL reconciliation under this extended model. We implemented our new algorithms and demonstrated up to 100 000-fold speed-up over existing methods, using both simulated and biological datasets. This dramatic improvement makes it possible to use DTL reconciliation for performing rigorous evolutionary analyses of large gene families and enables its use in advanced reconciliation-based gene and species tree reconstruction methods. © The Author(s) 2012. Published by Oxford University Press."
|
|
| |
 
Jesper Jansson and
Andrzej Lingas. Computing the rooted triplet distance between galled trees by counting triangles. In CPM12, Vol. 7354:385-398 of LNCS, springer, 2012.
Keywords: distance between networks, explicit network, from network, galled tree, phylogenetic network, phylogeny, polynomial, triplet distance.
Note: http://www.df.lth.se/~jj/Publications/d_rt_for_Galled_Trees5_CPM_2012.pdf.
Toggle abstract
"We consider a generalization of the rooted triplet distance between two phylogenetic trees to two phylogenetic networks. We show that if each of the two given phylogenetic networks is a so-called galled tree with n leaves then the rooted triplet distance can be computed in o(n 2.688) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance to that of counting monochromatic and almost- monochromatic triangles in an undirected, edge-colored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new related results that may be of independent interest. © 2012 Springer-Verlag."
|
|
| |
   
Tetsuo Asano,
Jesper Jansson,
Kunihiko Sadakane,
Ryuhei Uehara and
Gabriel Valiente. Faster computation of the Robinson–Foulds distance between phylogenetic networks. In Information Sciences, Vol. 197:77-90, 2012.
Keywords: distance between networks, explicit network, level k phylogenetic network, phylogenetic network, polynomial, spread.
Toggle abstract
"The Robinson-Foulds distance, a widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two phylogenetic networks N 1, N 2 with n leaf labels and at most m nodes and e edges each, the Robinson-Foulds distance measures the number of clusters of descendant leaves not shared by N 1 and N 2. The fastest known algorithm for computing the Robinson-Foulds distance between N 1 and N 2 runs in O(me) time. In this paper, we improve the time complexity to O(ne/log n) for general phylogenetic networks and O(nm/log n) for general phylogenetic networks with bounded degree (assuming the word RAM model with a word length of ⌈logn⌉ bits), and to optimal O(m) time for leaf-outerplanar networks as well as optimal O(n) time for level-1 phylogenetic networks (that is, galled-trees). We also introduce the natural concept of the minimum spread of a phylogenetic network and show how the running time of our new algorithm depends on this parameter. As an example, we prove that the minimum spread of a level-k network is at most k + 1, which implies that for one level-1 and one level-k phylogenetic network, our algorithm runs in O((k + 1)e) time. © 2012 Elsevier Inc. All rights reserved."
|
|
| |
Leo van Iersel,
Steven Kelk,
Nela Lekic and
Celine Scornavacca. A practical approximation algorithm for solving massive instances of hybridization number. In WABI12, Vol. 7534(430-440) of LNCS, springer, 2012.
Keywords: agreement forest, approximation, explicit network, from rooted trees, hybridization, phylogenetic network, phylogeny, Program CycleKiller, Program Dendroscope, Program HybridNET, reconstruction, software.
Note: http://arxiv.org/abs/1205.3417.
Toggle abstract
"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. In practice, exact solvers struggle to solve instances with reticulation number larger than 40. For such instances, one has to resort to heuristics and approximation algorithms. Here we present the algorithm CycleKiller which is the first approximation algorithm that can produce solutions verifiably close to optimality for instances with hundreds or even thousands of reticulations. Theoretically, the algorithm is an exponential-time 2-approximation (or 4-approximation in its fastest mode). However, using simulations we demonstrate that in practice the algorithm runs quickly for large and difficult instances, producing solutions within one percent of optimality. An implementation of this algorithm, which extends the theoretical work of [14], has been made publicly available. © 2012 Springer-Verlag."
|
|
| |
 
Lavanya Kannan and
Ward C Wheeler. Maximum Parsimony on Phylogenetic Networks. In ALMOB, Vol. 7:9, 2012.
Keywords: dynamic programming, explicit network, from sequences, heuristic, parsimony, phylogenetic network, phylogeny.
Note: http://dx.doi.org/10.1186/1748-7188-7-9.
Toggle abstract
"Background: Phylogenetic networks are generalizations of phylogenetic trees, that are used to model evolutionary events in various contexts. Several different methods and criteria have been introduced for reconstructing phylogenetic trees. Maximum Parsimony is a character-based approach that infers a phylogenetic tree by minimizing the total number of evolutionary steps required to explain a given set of data assigned on the leaves. Exact solutions for optimizing parsimony scores on phylogenetic trees have been introduced in the past.Results: In this paper, we define the parsimony score on networks as the sum of the substitution costs along all the edges of the network; and show that certain well-known algorithms that calculate the optimum parsimony score on trees, such as Sankoff and Fitch algorithms extend naturally for networks, barring conflicting assignments at the reticulate vertices. We provide heuristics for finding the optimum parsimony scores on networks. Our algorithms can be applied for any cost matrix that may contain unequal substitution costs of transforming between different characters along different edges of the network. We analyzed this for experimental data on 10 leaves or fewer with at most 2 reticulations and found that for almost all networks, the bounds returned by the heuristics matched with the exhaustively determined optimum parsimony scores.Conclusion: The parsimony score we define here does not directly reflect the cost of the best tree in the network that displays the evolution of the character. However, when searching for the most parsimonious network that describes a collection of characters, it becomes necessary to add additional cost considerations to prefer simpler structures, such as trees over networks. The parsimony score on a network that we describe here takes into account the substitution costs along the additional edges incident on each reticulate vertex, in addition to the substitution costs along the other edges which are common to all the branching patterns introduced by the reticulate vertices. Thus the score contains an in-built cost for the number of reticulate vertices in the network, and would provide a criterion that is comparable among all networks. Although the problem of finding the parsimony score on the network is believed to be computationally hard to solve, heuristics such as the ones described here would be beneficial in our efforts to find a most parsimonious network. © 2012 Kannan and Wheeler; licensee BioMed Central Ltd."
|
|
| |
Hyun Jung Park and
Luay Nakhleh. Inference of reticulate evolutionary histories by maximum likelihood:
The performance of information criteria. In RECOMB-CG'12, Vol. 13(suppl 19):S12 of BMCB, 2012.
Keywords: AIC, BIC, explicit network, heuristic, likelihood, phylogenetic network, phylogeny, reconstruction, statistical model.
Note: http://www.biomedcentral.com/1471-2105/13/S19/S12.
|
|
| |
Zhi-Zhong Chen,
Lusheng Wang and
Satoshi Yamanaka. A fast tool for minimum hybridization networks. In BMCB, Vol. 13:155, 2012.
Keywords: agreement forest, explicit network, from rooted trees, phylogenetic network, phylogeny, Program FastHN, reconstruction, software.
Note: http://dx.doi.org/10.1186/1471-2105-13-155.
Toggle abstract
"Background: Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to combine the two phylogenetic trees into a hybridization network with the fewest hybridization events. This leads to three computational problems, namely, the problem of computing the minimum size of a hybridization network, the problem of constructing one minimum hybridization network, and the problem of enumerating a representative set of minimum hybridization networks. The previously best software tools for these problems (namely, Chen and Wang's HybridNet and Albrecht et al.'s Dendroscope 3) run very slowly for large instances that cannot be reduced to relatively small instances. Indeed, when the minimum size of a hybridization network of two given trees is larger than 23 and the problem for the trees cannot be reduced to relatively smaller independent subproblems, then HybridNet almost always takes longer than 1 day and Dendroscope 3 often fails to complete. Thus, a faster software tool for the problems is in need.Results: We develop a software tool in ANSI C, named FastHN, for the following problems: Computing the minimum size of a hybridization network, constructing one minimum hybridization network, and enumerating a representative set of minimum hybridization networks. We obtain FastHN by refining HybridNet with three ideas. The first idea is to preprocess the input trees so that the trees become smaller or the problem becomes to solve two or more relatively smaller independent subproblems. The second idea is to use a fast algorithm for computing the rSPR distance of two given phylognetic trees to cut more branches of the search tree in the exhaustive-search stage of the algorithm. The third idea is that during the exhaustive-search stage of the algorithm, we find two sibling leaves in one of the two forests (obtained from the given trees by cutting some edges) such that they are as far as possible in the other forest. As the result, FastHN always runs much faster than HybridNet. Unlike Dendroscope 3, FastHN is a single-threaded program. Despite this disadvantage, our experimental data shows that FastHN runs substantially faster than the multi-threaded Dendroscope 3 on a PC with multiple cores. Indeed, FastHN can finish within 16 minutes (on average on a Windows-7 (x64) desktop PC with i7-2600 CPU) even if the minimum size of a hybridization network of two given trees is about 25, the trees each have 100 leaves, and the problem for the input trees cannot be reduced to two or more independent subproblems via cluster reductions. It is also worth mentioning that like HybridNet, FastHN does not use much memory (indeed, the amount of memory is at most quadratic in the input size). In contrast, Dendroscope 3 uses a huge amount of memory. Executables of FastHN for Windows XP (x86), Windows 7 (x64), Linux, and Mac OS are available (see the Results and discussion section for details).Conclusions: For both biological datasets and simulated datasets, our experimental results show that FastHN runs substantially faster than HybridNet and Dendroscope 3. The superiority of FastHN in speed over the previous tools becomes more significant as the hybridization number becomes larger. In addition, FastHN uses much less memory than Dendroscope 3 and uses the same amount of memory as HybridNet. © 2012 Chen et al.; licensee BioMed Central Ltd."
|
|
| |
 
Michel Habib and
Thu-Hien To. Constructing a Minimum Phylogenetic Network from a Dense Triplet Set. In JBCB, Vol. 10(5):1250013, 2012.
Keywords: explicit network, from triplets, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction.
Note: http://arxiv.org/abs/1103.2266.
Toggle abstract
"For a given set L of species and a set T of triplets on L, we seek to construct a phylogenetic network which is consistent with T i.e. which represents all triplets of T. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When T is dense, there exist polynomial time algorithms to construct level-0,1 and 2 networks (Aho et al., 1981; Jansson, Nguyen and Sung, 2006; Jansson and Sung, 2006; Iersel et al., 2009). For higher levels, partial answers were obtained in the paper by Iersel and Kelk (2008), with a polynomial time algorithm for simple networks. In this paper, we detail the first complete answer for the general case, solving a problem proposed in Jansson and Sung (2006) and Iersel et al. (2009). For any k fixed, it is possible to construct a level-k network having the minimum number of hybrid vertices and consistent with T, if there is any, in time O(|T| k+1 n⌊4k/3⌋+1). © 2012 Imperial College Press."
|
|
| |
    
Maureen Stolzer,
Han Lai,
Minli Xu,
Deepa Sathaye,
Benjamin Vernot and
Dannie Durand. Inferring Duplications, Losses, Transfers, and Incomplete Lineage Sorting with Non-Binary Species Trees. In ECCB12, Vol. 28(18):i409-i415 of BIO, 2012.
Keywords: duplication, explicit network, from rooted trees, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Notung, reconstruction.
Note: http://dx.doi.org/10.1093/bioinformatics/bts386.
Toggle abstract
"Motivation: Gene duplication (D), transfer (T), loss (L) and incomplete lineage sorting (I) are crucial to the evolution of gene families and the emergence of novel functions.The history of these events can be inferred via comparison of gene and species trees, a process called reconciliation, yet current reconciliation algorithms model only a subset of these evolutionary processes. Results: We present an algorithm to reconcile a binary gene tree with a nonbinary species tree under a DTLI parsimony criterion. This is the first reconciliation algorithm to capture all four evolutionary processes driving tree incongruence and the first to reconcile nonbinary species trees with a transfer model. Our algorithm infers all optimal solutions and reports complete, temporally feasible event histories, giving the gene and species lineages in which each event occurred. It is fixed-parameter tractable, with polytime complexity when the maximum species outdegree is fixed. Application of our algorithms to prokaryotic and eukaryotic data show that use of an incomplete event model has substantial impact on the events inferred and resulting biological conclusions. © The Author(s) 2012. Published by Oxford University Press."
|
|
| |
|
| |
Devin Robert Bickner. On normal networks. PhD thesis, Iowa State University, U.S.A., 2012.
Keywords: distance between networks, explicit network, from network, from trees, normal network, phylogenetic network, phylogeny, polynomial, reconstruction, SPR distance.
Note: http://gradworks.umi.com/3511361.pdf.
|
|
| |
|
| |
Adrià Alcalà Mena. Trivalent Graph isomorphism in polynomial time. Master's thesis, Universidad de Cantabria, Spain, 2012.
Keywords: distance between networks, explicit network, from network, isomorphism, phylogenetic network, phylogeny, polynomial, Program SAGE.
Note: http://arxiv.org/abs/1209.1040.
|
|
| |
 
Joseph K. Pickrell and
Jonathan K. Pritchard. Inference of Population Splits and Mixtures from Genome-Wide Allele Frequency Data. In PLoS Genetics, Vol. 8(11):e1002967, 2012.
Keywords: explicit network, heuristic, likelihood, phylogenetic network, phylogeny, population genetics, Program TreeMix.
Note: http://dx.doi.org/10.1371/journal.pgen.1002967.
Toggle abstract
"Many aspects of the historical relationships between populations in a species are reflected in genetic data. Inferring these relationships from genetic data, however, remains a challenging task. In this paper, we present a statistical model for inferring the patterns of population splits and mixtures in multiple populations. In our model, the sampled populations in a species are related to their common ancestor through a graph of ancestral populations. Using genome-wide allele frequency data and a Gaussian approximation to genetic drift, we infer the structure of this graph. We applied this method to a set of 55 human populations and a set of 82 dog breeds and wild canids. In both species, we show that a simple bifurcating tree does not fully describe the data; in contrast, we infer many migration events. While some of the migration events that we find have been detected previously, many have not. For example, in the human data, we infer that Cambodians trace approximately 16% of their ancestry to a population ancestral to other extant East Asian populations. In the dog data, we infer that both the boxer and basenji trace a considerable fraction of their ancestry (9% and 25%, respectively) to wolves subsequent to domestication and that East Asian toy breeds (the Shih Tzu and the Pekingese) result from admixture between modern toy breeds and "ancient" Asian breeds. Software implementing the model described here, called TreeMix, is available at http://treemix.googlecode.com. © 2012 Pickrell, Pritchard."
|
|
| |
   
Nick J. Patterson,
Priya Moorjani,
Yontao Luo,
Swapan Mallick,
Nadin Rohland,
Yiping Zhan,
Teri Genschoreck,
Teresa Webster and
David Reich. Ancient Admixture in Human History. In Genetics, Vol. 192(3):1065-1093, 2012.
Keywords: explicit network, phylogenetic network, phylogeny, population genetics, Program AdmixTools.
Note: http://genetics.med.harvard.edu/reich/Reich_Lab/Welcome_files/2012_Patterson_AncientAdmixture_Genetics.pdf.
Toggle abstract
"Population mixture is an important process in biology. We present a suite of methods for learning about population mixtures, implemented in a software package called ADMIXTOOLS, that support formal tests for whether mixture occurred and make it possible to infer proportions and dates of mixture. We also describe the development of a new single nucleotide polymorphism (SNP) array consisting of 629,433 sites with clearly documented ascertainment that was specifically designed for population genetic analyses and that we genotyped in 934 individuals from 53 diverse populations. To illustrate the methods, we give a number of examples that provide new insights about the history of human admixture. The most striking finding is a clear signal of admixture into northern Europe, with one ancestral population related to present-day Basques and Sardinians and the other related to present-day populations of northeast Asia and the Americas. This likely reflects a history of admixture between Neolithic migrants and the indigenous Mesolithic population of Europe, consistent with recent analyses of ancient bones from Sweden and the sequencing of the genome of the Tyrolean "Iceman." © 2012 by the Genetics Society of America."
|
|
| |
  
Katharina Huber,
Vincent Moulton,
Andreas Spillner,
Sabine Storandt and
Radoslaw Suchecki. Computing a consensus of multilabeled trees. In ALENEX12, Pages 84-92, 2012.
Keywords: duplication, explicit network, exponential algorithm, phylogenetic network, phylogeny.
Note: http://siam.omnibooksonline.com/2012ALENEX/data/papers/020.pdf.
Toggle abstract
In this paper we consider two challenging problems that arise in the context of computing a consensus of a collection of multilabeled trees, namely (1) selecting a compatible collection of clusters on a multiset from an ordered list of such clusters and (2) optimally refining high degree vertices in a multilabeled tree. Forming such a consensus is part of an approach to reconstruct the evolutionary history of a set of species for which events such as genome duplication and hybridization have occurred in the past. We present exact algorithms for solving (1) and (2) that have an exponential run-time in the worst case. To give some impression of their performance in practice, we apply them to simulated input and to a real biological data set highlighting the impact of several structural properties of the input on the performance.
|
|
| |
|
| |
Zhi-Zhong Chen,
Fei Deng and
Lusheng Wang. Simultaneous Identification of Duplications, Losses, and Lateral Gene Transfers. In TCBB, Vol. 9(5):1515-1528, 2012.
Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, reconstruction.
Note: http://www.cs.cityu.edu.hk/~lwang/research/tcbb2012c.pdf.
Toggle abstract
"We give a fixed-parameter algorithm for the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m+3 k/c n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCA-reconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m+2.78 k/cn). © 2004-2012 IEEE."
|
|
| |
|
|
- forked on GitHub.