|

Louxin Zhang. Recent Progresses in the Combinatorial and Algorithmic Study of Rooted Phylogenetic Networks. In WALCOM20, Vol. 12049:22-27 of LNCS, Springer, 2020. Keywords: cluster containment, galled network, galled tree, nearly-stable network, phylogenetic network, phylogeny, polynomial, reticulation-visible network, survey, time consistent network, tree containment, tree-based network, tree-child network.
|
|
|
  
Remie Janssen,
Mark Jones and
Yukihiro Murakami. Combining Networks Using Cherry Picking Sequences. In AlCoB20, Vol. 12099:77-92 of LNCS, Springer, 2020. Keywords: cherry-picking, explicit network, FPT, from network, hybridization, orchard network, phylogenetic network, phylogeny, tree-child network.
|
|
|
 
Remie Janssen and
Yukihiro Murakami. Linear Time Algorithm for Tree-Child Network Containment. In AlCoB20, Vol. 12099:93-107 of LNCS, Springer, 2020. Keywords: explicit network, from network, isomorphism, phylogenetic network, phylogeny, polynomial, reconstruction, tree-child network, tree-child sequence. Note: https://doi.org/10.1007/978-3-030-42266-0_8.
|
|
|
|
|
 
Juan Wang and
Maozu Guo. IGNet: Constructing Rooted Phylogenetic Networks Based on Incompatible Graphs. In ICNC-FSKD19, Vol. 1075:894-900 of Advances in Intelligent Systems and Computing, Springer, 2019. Keywords: explicit network, from rooted trees, phylogenetic network, phylogeny, Program BIMLR, Program IGNet, Program LNetwork, reconstruction, software.
|
|
|
 
Jesper Jansson,
Konstantinos Mampentzidis,
Ramesh Rajaby and
Wing-Kin Sung. Computing the Rooted Triplet Distance Between Phylogenetic Networks. In IWOCA19, Vol. 11638:290-303 of LNCS, Springer, 2019. Keywords: distance between networks, from network, phylogenetic network, phylogeny, polynomial, triplet distance.
|
|
|

Mathias Weller. Linear-Time Tree Containment in Phylogenetic Networks. In RECOMB-CG18, Vol. 11183:309-323 of LNCS, Springer, 2018. Keywords: explicit network, from network, from rooted trees, nearly-stable network, phylogenetic network, phylogeny, polynomial, reconstruction, reticulation-visible network, tree containment. Note: https://arxiv.org/abs/1702.06364.
|
|
|
   
Hussein A. Hejase,
Natalie VandePol,
Gregory A. Bonito and
Kevin J. Liu. Fast and accurate statistical inference of phylogenetic networks using large-scale genomic sequence data. In RECOMB-CG18, Vol. 11183:242-259 of LNCS, Springer, 2018. Keywords: explicit network, from rooted trees, heuristic, phylogenetic network, phylogeny, Program FastNet, reconstruction. Note: http://biorxiv.org/content/early/2017/05/01/132795.
|
|
|

Andreas Gunawan. Solving the Tree Containment Problem for Reticulation-visible Networks in Linear Time. In AlCoB18, Vol. 10849:24-36 of LNCS, Springer, 2018. Keywords: explicit network, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulation-visible network, tree containment. Note: https://arxiv.org/abs/1702.04088.
|
|
|
 
Sebastien Roch and
Kun-Chieh Wang. Circular Networks from Distorted Metrics. In RECOMB18, Vol. 10812:167-176 of LNCS, Springer, 2018. Keywords: abstract network, circular split system, from distances, NeighborNet, phylogenetic network, phylogeny, reconstruction, split network. Note: https://arxiv.org/abs/1707.05722.
|
|
|
    
Leo van Iersel,
Remie Janssen,
Mark Jones,
Yukihiro Murakami and
Norbert Zeh. Polynomial-Time Algorithms for Phylogenetic Inference Problems. In AlCoB18, Vol. 10849:37-49 of LNCS, Springer, 2018. Keywords: hybridization, minimum number, parental hybridization, phylogenetic network, phylogeny, polynomial, reconstruction, weakly displaying. Note: https://research.tudelft.nl/files/53686721/10.1007_978_3_319_91938_6_4.pdf.
|
|
|
  
Bingxin Lu,
Louxin Zhang and
Hon Wai Leong. A program to compute the soft Robinson-Foulds distance between phylogenetic networks. In APBC17, Vol. 18(Suppl. 2):111 of BMC Genomics, 2017. Keywords: cluster containment, distance between networks, explicit network, exponential algorithm, from network, phylogenetic network, phylogeny, Program icelu-PhyloNetwork. Note: http://dx.doi.org/10.1186/s12864-017-3500-5.
|
|
|
 
Jesper Jansson,
Ramesh Rajaby and
Wing-Kin Sung. An Efficient Algorithm for the Rooted Triplet Distance Between Galled Trees. In AlCoB17, Vol. 10252:115-126 of LNCS, Springer, 2017. Keywords: distance between networks, from network, phylogenetic network, phylogeny, polynomial, reconstruction, triplet distance. Note: .
|
|
|
     
Philippe Gambette,
Leo van Iersel,
Mark Jones,
Manuel Lafond,
Fabio Pardi and
Celine Scornavacca. Rearrangement Moves on Rooted Phylogenetic Networks. In PLoS Computational Biology, Vol. 13(8):e1005611.1-21, 2017. Keywords: distance between networks, explicit network, from network, NNI distance, NNI moves, phylogenetic network, phylogeny, SPR distance. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-01572624/en/.
|
|
|
  
Han Lai,
Maureen Stolzer and
Dannie Durand. Fast Heuristics for Resolving Weakly Supported Branches Using Duplication, Transfers, and Losses. In RECOMB-CG17, Vol. 10562:298-320 of LNCS, Springer, 2017. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, phylogenetic network, phylogeny, Program Notung, reconstruction.
|
|
|
|
|
|
|
  
Kuang-Yu Chang,
Yun Cui,
Siu-Ming Yiu and
Wing-Kai Hon. Reconstructing One-Articulated Networks with Distance Matrices. In ISBRA17, Vol. 10330:34-45 of LNCS, Springer, 2017. Keywords: explicit network, from distances, k-reticulated, phylogenetic network, phylogeny, reconstruction. Note: https://link.springer.com/content/pdf/10.1007%2F978-3-319-59575-7.pdf#page=100.
|
|
|
  
Andreas Gunawan,
Bhaskar DasGupta and
Louxin Zhang. Locating a Tree in a Reticulation-Visible Network in Cubic Time. In RECOMB16, Vol. 9649:266 of LNBI, Springer, 2016. Keywords: cluster containment, explicit network, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, reticulation-visible network, tree containment. Note: http://arxiv.org/abs/1507.02119.
|
|
|
    
Philippe Gambette,
Andreas Gunawan,
Anthony Labarre,
Stéphane Vialette and
Louxin Zhang. Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time. In IWOCA15, Vol. 9538:197-208 of LNCS, springer, 2016. Keywords: explicit network, from network, from rooted trees, genetically stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal-upec-upem.archives-ouvertes.fr/hal-01226035 .
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
    
Philippe Gambette,
Andreas Gunawan,
Anthony Labarre,
Stéphane Vialette and
Louxin Zhang. Locating a Tree in A Phylogenetic Network in Quadratic Time. In RECOMB15, Vol. 9029:96-107 of LNCS, Springer, 2015. Keywords: evaluation, explicit network, from network, from rooted trees, genetically stable network, nearly-stable network, phylogenetic network, phylogeny, polynomial, tree containment. Note: https://hal.archives-ouvertes.fr/hal-01116231/en.
|
|
|
|
|
 
Quan Nguyen and
Teemu Roos. Likelihood-based inference of phylogenetic networks from sequence data by PhyloDAG. In AlCoB15, Vol. 9199:126-140 of LNCS, springer, 2015. Keywords: BIC, explicit network, from sequences, likelihood, phylogenetic network, phylogeny, Program PhyloDAG, reconstruction, software. Note: http://www.cs.helsinki.fi/u/ttonteri/pub/alcob2015.pdf.
|
|
|
|
|
 
Misagh Kordi and
Mukul S. Bansal. On the Complexity of Duplication-Transfer-Loss Reconciliation with Non-Binary Gene Trees. In ISBRA15, Vol. 9096:187-198 of LNCS, springer, 2015. Keywords: duplication, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, phylogenetic network, phylogeny, reconstruction. Note: http://compbio.engr.uconn.edu/papers/Kordi_ISBRA2015.pdf.
|
|
|
|
|
    
Gergely J. Szöllösi,
Adrián Arellano Davín,
Eric Tannier,
Vincent Daubin and
Bastien Boussau. Genome-scale phylogenetic analysis finds extensive gene transfer among fungi. In Philosophical Transactions of the Royal Society of London B: Biological Sciences, Vol. 370(1678):1-11, 2015. Keywords: duplication, from sequences, lateral gene transfer, loss, phylogenetic network, phylogeny, Program ALE, reconstruction. Note: http://dx.doi.org/10.1098/rstb.2014.0335.
|
|
|
|
|
 
Jessica W. Leigh and
David Bryant. PopART: full-feature software for haplotype network construction. In Methods in Ecology and Evolution, Vol. 6(9):1110-1116, 2015. Keywords: abstract network, from sequences, haplotype network, MedianJoining, phylogenetic network, phylogeny, population genetics, Program PopART, Program TCS, software. Note: http://dx.doi.org/10.1111/2041-210X.12410.
|
|
|
 
Leo van Iersel and
Steven Kelk. Kernelizations for the hybridization number problem on multiple nonbinary trees. In WG14, Vol. 8747:299-311 of LNCS, springer, 2014. Keywords: explicit network, from rooted trees, kernelization, minimum number, phylogenetic network, phylogeny, Program Treeduce, reconstruction. Note: http://arxiv.org/abs/1311.4045.
|
|
|
   
Ran Libeskind-Hadas,
Yi-Chieh Wu,
Mukul S. Bansal and
Manolis Kellis. Pareto-optimal phylogenetic tree reconciliation. In ISMB14, Vol. 30:i87-i95 of BIO, 2014. Keywords: duplication, lateral gene transfer, loss, phylogenetic network, phylogeny, polynomial, Program Xscape, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/btu289.
Toggle abstract
"Motivation: Phylogenetic tree reconciliation is a widely used method for reconstructing the evolutionary histories of gene families and species, hosts and parasites and other dependent pairs of entities. Reconciliation is typically performed using maximum parsimony, in which each evolutionary event type is assigned a cost and the objective is to find a reconciliation of minimum total cost. It is generally understood that reconciliations are sensitive to event costs, but little is understood about the relationship between event costs and solutions. Moreover, choosing appropriate event costs is a notoriously difficult problem. Results: We address this problem by giving an efficient algorithm for computing Pareto-optimal sets of reconciliations, thus providing the first systematic method for understanding the relationship between event costs and reconciliations. This, in turn, results in new techniques for computing event support values and, for cophylogenetic analyses, performing robust statistical tests. We provide new software tools and demonstrate their use on a number of datasets from evolutionary genomic and cophylogenetic studies. © 2014 The Author. Published by Oxford University Press. All rights reserved."
|
|
|

Yufeng Wu. An Algorithm for Constructing Parsimonious Hybridization Networks with Multiple Phylogenetic Trees. In RECOMB13, Vol. 7821:291-303 of LNCS, springer, 2013. Keywords: explicit network, exponential algorithm, from rooted trees, phylogenetic network, phylogeny, Program PIRN, reconstruction. Note: http://www.engr.uconn.edu/~ywu/Papers/ExactNetRecomb2013.pdf.
Toggle abstract
"Phylogenetic network is a model for reticulate evolution. Hybridization network is one type of phylogenetic network for a set of discordant gene trees, and "displays" each gene tree. A central computational problem on hybridization networks is: given a set of gene trees, reconstruct the minimum (i.e. most parsimonious) hybridization network that displays each given gene tree. This problem is known to be NP-hard, and existing approaches for this problem are either heuristics or make simplifying assumptions (e.g. work with only two input trees or assume some topological properties). In this paper, we develop an exact algorithm (called PIRNC ) for inferring the minimum hybridization networks from multiple gene trees. The PIRNC algorithm does not rely on structural assumptions. To the best of our knowledge, PIRN C is the first exact algorithm for this formulation. When the number of reticulation events is relatively small (say four or fewer), PIRNC runs reasonably efficient even for moderately large datasets. For building more complex networks, we also develop a heuristic version of PIRNC called PIRNCH. Simulation shows that PIRNCH usually produces networks with fewer reticulation events than those by an existing method. © 2013 Springer-Verlag."
|
|
|
|
|
     
Hoa Vu,
Francis Chin,
Wing-Kai Hon,
Henry Leung,
Kunihiko Sadakane,
Wing-Kin Sung and
Siu-Ming Yiu. Reconstructing k-Reticulated Phylogenetic Network from a Set of Gene Trees. In ISBRA13, Vol. 7875:112-124 of LNCS, springer, 2013. Keywords: from rooted trees, k-reticulated, phylogenetic network, phylogeny, polynomial, Program ARTNET, Program CMPT, reconstruction. Note: http://grid.cs.gsu.edu/~xguo9/publications/2013_Cloud%20computing%20for%20de%20novo%20metagenomic%20sequence%20assembly.pdf#page=123.
Toggle abstract
"The time complexity of existing algorithms for reconstructing a level-x phylogenetic network increases exponentially in x. In this paper, we propose a new classification of phylogenetic networks called k-reticulated network. A k-reticulated network can model all level-k networks and some level-x networks with x > k. We design algorithms for reconstructing k-reticulated network (k = 1 or 2) with minimum number of hybrid nodes from a set of m binary trees, each with n leaves in O(mn 2) time. The implication is that some level-x networks with x > k can now be reconstructed in a faster way. We implemented our algorithm (ARTNET) and compared it with CMPT. We show that ARTNET outperforms CMPT in terms of running time and accuracy. We also consider the case when there does not exist a 2-reticulated network for the input trees. We present an algorithm computing a maximum subset of the species set so that a new set of subtrees can be combined into a 2-reticulated network. © 2013 Springer-Verlag."
|
|
|
  
Mukul S. Bansal,
Eric J. Alm and
Manolis Kellis. Reconciliation Revisited: Handling Multiple Optima when Reconciling with Duplication, Transfer, and Loss. In JCB, Vol. 20(10):738-754, 2013. Keywords: duplication, from rooted trees, from species tree, loss, phylogenetic network, phylogeny, Program RANGER-DTL, reconstruction. Note: http://www.engr.uconn.edu/~mukul/Bansal_JCB2013.pdf.
Toggle abstract
"Phylogenetic tree reconciliation is a powerful approach for inferring evolutionary events like gene duplication, horizontal gene transfer, and gene loss, which are fundamental to our understanding of molecular evolution. While duplication-loss (DL) reconciliation leads to a unique maximum-parsimony solution, duplication-transfer-loss (DTL) reconciliation yields a multitude of optimal solutions, making it difficult to infer the true evolutionary history of the gene family. This problem is further exacerbated by the fact that different event cost assignments yield different sets of optimal reconciliations. Here, we present an effective, efficient, and scalable method for dealing with these fundamental problems in DTL reconciliation. Our approach works by sampling the space of optimal reconciliations uniformly at random and aggregating the results. We show that even gene trees with only a few dozen genes often have millions of optimal reconciliations and present an algorithm to efficiently sample the space of optimal reconciliations uniformly at random in O(mn 2) time per sample, where m and n denote the number of genes and species, respectively. We use these samples to understand how different optimal reconciliations vary in their node mappings and event assignments and to investigate the impact of varying event costs. We apply our method to a biological dataset of approximately 4700 gene trees from 100 taxa and observe that 93% of event assignments and 73% of mappings remain consistent across different multiple optima. Our analysis represents the first systematic investigation of the space of optimal DTL reconciliations and has many important implications for the study of gene family evolution. © 2013 Mary Ann Liebert, Inc."
|
|
|
|
|
 
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."
|
|
|
    
An-Chiang Chu,
Jesper Jansson,
Richard Lemence,
Alban Mancheron and
Kun-Mao Chao. Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics. In TAMC12, Vol. 7287:177-188 of LNCS, springer, 2012. Keywords: from triplets, galled network, level k phylogenetic network, phylogenetic network. Note: preliminary version.
Toggle abstract
"We study the asymptotic behavior of a new type of maximization recurrence, defined as follows. Let k be a positive integer and p k(x) a polynomial of degree k satisfying p k(0) = 0. Define A 0 = 0 and for n ≥ 1, let A n = max 0≤i<n{A i+n kp k(i/n)}. We prove that lim n→∞A n/n n = sup{pk(x)/1-x k : 0≤x<1}. We also consider two closely related maximization recurrences S n and S′ n, defined as S 0 = S′ 0 = 0, and for n ≥ 1, S n = max 0≤i<n{S i + i(n-i)(n-i-1)/2} and S′ n = max 0≤i<n{S′ i + ( 3 n-i) + 2i( 2 n-i) + (n-i)( 2 i)}. We prove that lim n→∞ S′n/3( 3 n) = 2(√3-1)/3 ≈ 0.488033..., resolving an open problem from Bioinformatics about rooted triplets consistency in phylogenetic networks. © 2012 Springer-Verlag."
|
|
|
|
|
 
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."
|
|
|
 
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.
|
|
|
    
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."
|
|
|
    
Thi-Hau Nguyen,
Jean-Philippe Doyon,
Stéphanie Pointet,
Anne-Muriel Chifolleau Arigon,
Vincent Ranwez and
Vincent Berry. Accounting for Gene Tree Uncertainties Improves Gene Trees and Reconciliation Inference. In WABI12, Vol. 7534:123-134 of LNCS, springer, 2012. Keywords: duplication, heuristic, lateral gene transfer, phylogenetic network, phylogeny, Program Mowgli, reconstruction. Note: http://hal.archives-ouvertes.fr/hal-00718347/en/.
Toggle abstract
"We propose a reconciliation heuristic accounting for gene duplications, losses and horizontal transfers that specifically takes into account the uncertainties in the gene tree. Rearrangements are tried for gene tree edges that are weakly supported, and are accepted whenever they improve the reconciliation cost. We prove useful properties on the dynamic programming matrix used to compute reconciliations, which allows to speed-up the tree space exploration when rearrangements are generated by Nearest Neighbor Interchanges (NNI) edit operations. Experimental results on simulated and real data confirm that running times are greatly reduced when considering the above-mentioned optimization in comparison to the naïve rearrangement procedure. Results also show that gene trees modified by such NNI rearrangements are closer to the correct (simulated) trees and lead to more correct event predictions on average. The program is available at http://www.atgc-montpellier.fr/ Mowgli/. © 2012 Springer-Verlag."
|
|
|
   
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.
|
|
|

Cayla McBee. Generalizing Fourier Calculus on Evolutionary Trees to Splits Networks. In ISPAN'12, Pages 149-155, 2012. Keywords: abstract network, from sequences, phylogenetic network, phylogeny, split network, statistical model.
Toggle abstract
"Biologists have been interested in Phylogenetics, the study of evolutionary relatedness among various groups of organisms, for more than 140 years. In spite of this, it has only been in the last 40 years that advances in technology and the availability of DNA sequences have led to statistical, computational and algorithmic work on determining evolutionary relatedness between organisms. One method of determining historical relationships between organisms is to assume a group based evolutionary model and use a discrete Fourier transform. The 1993 paper 'Fourier Calculus on Evolutionary Trees' by L.A. Szekely, M.A. Steel and P.L. Erdos outlines this process. The transform presented in Szekely et al provides an invertible relationship between phylogenetic trees and expected frequencies of nucleotide patterns in nucleotide sequences. This implies that given a set of nucleotide sequences from various organisms it is possible to construct a phylogenetic tree that represents the historical relationships of those organisms. Some scenarios are poorly described by phylogenetic trees and there are biological and statistical reasons for using networks to model phylogenetic relationships. Given this motivation I have generalized Szekely et al's result to apply to a specific type of phylogenetic network known as a splits network. © 2012 IEEE."
|
|
|
  
Fenglou Mao,
David Williams,
Olga Zhaxybayeva,
Maria S. Poptsova,
Pascal Lapierre,
J. Peter Gogarten and
Ying Xu. Quartet decomposition server: a platform for analyzing phylogenetic trees. In BMCB, Vol. 13:123, 2012. Keywords: abstract network, from quartets, phylogenetic network, phylogeny, Program Quartet Decomposition, reconstruction, software, split network.
Toggle abstract
"Background: The frequent exchange of genetic material among prokaryotes means that extracting a majority or plurality phylogenetic signal from many gene families, and the identification of gene families that are in significant conflict with the plurality signal is a frequent task in comparative genomics, and especially in phylogenomic analyses. Decomposition of gene trees into embedded quartets (unrooted trees each with four taxa) is a convenient and statistically powerful technique to address this challenging problem. This approach was shown to be useful in several studies of completely sequenced microbial genomes.Results: We present here a web server that takes a collection of gene phylogenies, decomposes them into quartets, generates a Quartet Spectrum, and draws a split network. Users are also provided with various data download options for further analyses. Each gene phylogeny is to be represented by an assessment of phylogenetic information content, such as sets of trees reconstructed from bootstrap replicates or sampled from a posterior distribution. The Quartet Decomposition server is accessible at http://quartets.uga.edu.Conclusions: The Quartet Decomposition server presented here provides a convenient means to perform Quartet Decomposition analyses and will empower users to find statistically supported phylogenetic conflicts. © 2012 Mao et al.; licensee BioMed Central Ltd."
|
|
|
    
Jean-Philippe Doyon,
Celine Scornavacca,
Konstantin Yu Gorbunov,
Gergely J. Szöllösi,
Vincent Ranwez and
Vincent Berry. An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications, and transfers. In Proceedings of the Eighth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'10), Vol. 6398:93-108 of LNCS, springer, 2011. Keywords: branch length, duplication, dynamic programming, explicit network, from multilabeled tree, from species tree, from unrooted trees, lateral gene transfer, loss, phylogenetic network, phylogeny, polynomial, Program Mowgli, reconstruction. Note: http://www.lirmm.fr/~vberry/Publis/MPR-DoyonEtAl.pdf, software available at http://www.atgc-montpellier.fr/MPR/.
Toggle abstract
"Tree reconciliation methods aim at estimating the evolutionary events that cause discrepancy between gene trees and species trees. We provide a discrete computational model that considers duplications, transfers and losses of genes. The model yields a fast and exact algorithm to infer time consistent and most parsimonious reconciliations. Then we study the conditions under which parsimony is able to accurately infer such events. Overall, it performs well even under realistic rates, transfers being in general less accurately recovered than duplications. An implementation is freely available at http://www.atgc- montpellier.fr/MPR. © 2010 Springer-Verlag."
|
|
|
  
Mukul S. Bansal,
J. Peter Gogarten and
Ron Shamir. Detecting Highways of Horizontal Gene Transfer. In Proceedings of the Eighth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'10), Vol. 6398:109-120 of LNCS, springer, 2011. Keywords: explicit network, from rooted trees, from species tree, lateral gene transfer, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.cs.iastate.edu/~bansal/Highways_RCG10.pdf.
Toggle abstract
"In a horizontal gene transfer (HGT) event a gene is transferred between two species that do not share an ancestor-descendant relationship. Typically, no more than a few genes are horizontally transferred between any two species. However, several studies identified pairs of species between which many different genes were horizontally transferred. Such a pair is said to be linked by a highway of gene sharing. We present a method for inferring such highways. Our method is based on the fact that the evolutionary histories of horizontally transferred genes disagree with the corresponding species phylogeny. Specifically, given a set of gene trees and a trusted rooted species tree, each gene tree is first decomposed into its constituent quartet trees and the quartets that are inconsistent with the species tree are identified. Our method finds a pair of species such that a highway between them explains the largest (normalized) fraction of inconsistent quartets. For a problem on n species, our method requires O(n 4) time, which is optimal with respect to the quartets input size. An application of our method to a dataset of 1128 genes from 11 cyanobacterial species, as well as to simulated datasets, illustrates the efficacy of our method. © 2010 Springer-Verlag."
|
|
|
 
Celine Scornavacca,
Franziska Zickmann and
Daniel H. Huson. Tanglegrams for Rooted Phylogenetic Trees and Networks. In ISMB11, Vol. 27(13):i248-i256 of BIO, 2011. Keywords: from network, heuristic, integer linear programming, phylogenetic network, phylogeny, Program Dendroscope, tanglegram, visualization. Note: http://dx.doi.org/10.1093/bioinformatics/btr210.
Toggle abstract
"Motivation: In systematic biology, one is often faced with the task of comparing different phylogenetic trees, in particular in multi-gene analysis or cospeciation studies. One approach is to use a tanglegram in which two rooted phylogenetic trees are drawn opposite each other, using auxiliary lines to connect matching taxa. There is an increasing interest in using rooted phylogenetic networks to represent evolutionary history, so as to explicitly represent reticulate events, such as horizontal gene transfer, hybridization or reassortment. Thus, the question arises how to define and compute a tanglegram for such networks. Results: In this article, we present the first formal definition of a tanglegram for rooted phylogenetic networks and present a heuristic approach for computing one, called the NN-tanglegram method. We compare the performance of our method with existing tree tanglegram algorithms and also show a typical application to real biological datasets. For maximum usability, the algorithm does not require that the trees or networks are bifurcating or bicombining, or that they are on identical taxon sets. © The Author(s) 2011. Published by Oxford University Press."
|
|
|
 
Lawrence A. David and
Eric J. Alm. Rapid evolutionary innovation during an Archaean genetic expansion. In Nature, Vol. 469:93-96, 2011. Keywords: duplication, dynamic programming, from multilabeled tree, from rooted trees, from species tree, parsimony, phylogenetic network, phylogeny, Program Angst. Note: http://dx.doi.org/10.1038/nature09649, Program Angst described here.
|
|
|
 
Changiz Eslahchi and
Reza Hassanzadeh. New Algorithm for Constructing Supernetworks from Partial Trees. In MCCMB11, Pages 106-107, 2011. Keywords: abstract network, from unrooted trees, heuristic, phylogenetic network, phylogeny, Program SNSA, reconstruction, simulated annealing, split network. Note: http://mccmb.belozersky.msu.ru/2011/mccmb11.pdf#page=106.
|
|
|
   
Louxin Zhang,
Yen Kaow Ng,
Taoyang Wu and
Yu Zheng. Network model and efficient method for detecting relative duplications or horizontal gene transfers. In ICCABS11, Pages 214-219, 2011. Keywords: dynamic programming, explicit network, from network, from rooted trees, from species tree, phylogenetic network, phylogeny, polynomial, reconstruction.
Toggle abstract
"Background: Horizontal gene transfer and gene duplication are two significant forces behind genome evolution. As more and more well-supported examples of HGTs are being revealed, there is a growing awareness that HGT is more widespread than previously thought, occurring often not only within bacteria, but also between species remotely related such as bacteria and plants or plants and animals. Although a substantial number of genomic sequences are known, HGT inference remains challenging. Parsimony-based inferences of HGT events are typically NP-hard under the framework of gene tree and species tree comparison; it is even more timeconsuming if the maximum likelihood approach is used. The fact that gene tree and species tree incongruence can be further confounded by gene duplication and gene loss events motivates us to incorporate considerations for these events into our inference of HGT events. Similarly, it will be beneficial if known HGT events are considered in the inference of gene duplications and gene losses. © 2011 IEEE."
|
|
|

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."
|
|
|
   
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."
|
|
|
   
Leo van Iersel,
Steven Kelk,
Regula Rupp and
Daniel H. Huson. Phylogenetic Networks Do not Need to Be Complex: Using Fewer Reticulations to Represent Conflicting Clusters. In ISMB10, Vol. 26(12):i124-i131 of BIO, 2010. Keywords: from clusters, level k phylogenetic network, Program Dendroscope, Program HybridInterleave, Program HybridNumber, reconstruction. Note: http://dx.doi.org/10.1093/bioinformatics/btq202, with proofs: http://arxiv.org/abs/0910.3082.
Toggle abstract
"Phylogenetic trees are widely used to display estimates of how groups of species are evolved. Each phylogenetic tree can be seen as a collection of clusters, subgroups of the species that evolved from a common ancestor. When phylogenetic trees are obtained for several datasets (e.g. for different genes), then their clusters are often contradicting. Consequently, the set of all clusters of such a dataset cannot be combined into a single phylogenetic tree. Phylogenetic networks are a generalization of phylogenetic trees that can be used to display more complex evolutionary histories, including reticulate events, such as hybridizations, recombinations and horizontal gene transfers. Here, we present the new CASS algorithm that can combine any set of clusters into a phylogenetic network. We show that the networks constructed by CASS are usually simpler than networks constructed by other available methods. Moreover, we show that CASS is guaranteed to produce a network with at most two reticulations per biconnected component, whenever such a network exists. We have implemented CASS and integrated it into the freely available Dendroscope software. Contact: l.j.j.v.iersel@gmail.com. Supplementary information: Supplementary data are available at Bioinformatics online. © The Author(s) 2010. Published by Oxford University Press."
|
|
|
    
Tetsuo Asano,
Jesper Jansson,
Kunihiko Sadakane,
Ryuhei Uehara and
Gabriel Valiente. Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks. In CPM10, Vol. 6129:190-201 of LNCS, springer, 2010. Keywords: distance between networks, explicit network, level k phylogenetic network, phylogenetic network, polynomial, spread. Note: http://hdl.handle.net/10119/9859, slides available at http://cs.nyu.edu/parida/CPM2010/MainPage_files/18.pdf.
Toggle abstract
"The Robinson-Foulds distance, which is the most widely used metric for comparing phylogenetic trees, has recently been generalized to phylogenetic networks. Given two networks N1,N2 with n leaves, m nodes, and e edges, the Robinson-Foulds distance measures the number of clusters of descendant leaves that are not shared by N1 and N2. The fastest known algorithm for computing the Robinson-Foulds distance between those networks runs in O(m(m + e)) time. In this paper, we improve the time complexity to O(n(m+ e)/ log n) for general networks and O(nm/log n) for general networks with bounded degree, and to optimal O(m + e) time for planar phylogenetic networks and boundedlevel phylogenetic networks.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 phylogenetic network is at most k + 1, which implies that for two level-k phylogenetic networks, our algorithm runs in O((k + 1)(m + e)) time. © Springer-Verlag Berlin Heidelberg 2010."
|
|
|

Yufeng Wu. Close Lower and Upper Bounds for the Minimum Reticulate Network of Multiple Phylogenetic Trees. In ISMB10, Vol. 26(12):i140-i148 of BIO, 2010. Keywords: explicit network, from rooted trees, hybridization, minimum number, phylogenetic network, phylogeny, Program PIRN, software. Note: http://dx.doi.org/10.1093/bioinformatics/btq198.
Toggle abstract
"Motivation: Reticulate network is a model for displaying and quantifying the effects of complex reticulate processes on the evolutionary history of species undergoing reticulate evolution. A central computational problem on reticulate networks is: given a set of phylogenetic trees (each for some region of the genomes), reconstruct the most parsimonious reticulate network (called the minimum reticulate network) that combines the topological information contained in the given trees. This problem is well-known to be NP-hard. Thus, existing approaches for this problem either work with only two input trees or make simplifying topological assumptions. Results: We present novel results on the minimum reticulate network problem. Unlike existing approaches, we address the fully general problem: there is no restriction on the number of trees that are input, and there is no restriction on the form of the allowed reticulate network. We present lower and upper bounds on the minimum number of reticulation events in the minimum reticulate network (and infer an approximately parsimonious reticulate network). A program called PIRN implements these methods, which also outputs a graphical representation of the inferred network. Empirical results on simulated and biological data show that our methods are practical for a wide range of data. More importantly, the lower and upper bounds match for many datasets (especially when the number of trees is small or reticulation level is low), and this allows us to solve the minimum reticulate network problem exactly for these datasets. Availability: A software tool, PIRN, is available for download from the web page: http://www.engr.uconn.edu/ywu. Contact: ywu@engr.uconn.edu. Supplementary information: Supplementary data is available at Bioinformatics online. © The Author(s) 2010. Published by Oxford University Press."
|
|
|

Yufeng Wu and
Jiayin Wang. Fast Computation of the Exact Hybridization Number of Two Phylogenetic Trees. In ISBRA10, Vol. 6053:203-214 of LNCS, springer, 2010. Keywords: agreement forest, explicit network, from rooted trees, hybridization, integer linear programming, minimum number, phylogenetic network, phylogeny, Program HybridNumber, Program SPRDist, SPR distance. Note: http://www.engr.uconn.edu/~ywu/Papers/ISBRA10WuWang.pdf.
Toggle abstract
"Hybridization is a reticulate evolutionary process. An established problem on hybridization is computing the minimum number of hybridization events, called the hybridization number, needed in the evolutionary history of two phylogenetic trees. This problem is known to be NP-hard. In this paper, we present a new practical method to compute the exact hybridization number. Our approach is based on an integer linear programming formulation. Simulation results on biological and simulated datasets show that our method (as implemented in program SPRDist) is more efficient and robust than an existing method. © 2010 Springer-Verlag Berlin Heidelberg."
|
|
|
 
Thu-Hien To and
Michel Habib. Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time. In CPM09, (5577):275-288, springer, 2009. Keywords: explicit network, from triplets, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://arxiv.org/abs/0901.1657.
Toggle abstract
"For a given dense triplet set Τ there exist two natural questions [7]: Does there exist any phylogenetic network consistent with Τ? In case such networks exist, can we find an effective algorithm to construct one? For cases of networks of levels k = 0, 1 or 2, these questions were answered in [1,6,7,8,10] with effective polynomial algorithms. For higher levels k, partial answers were recently obtained in [11] with an O(/Τ/k+1)time algorithm for simple networks. In this paper, we give a complete answer to the general case, solving a problem proposed in [7]. The main idea of our proof is to use a special property of SN-sets in a level-k network. As a consequence, for any fixed k, we can also find a level-k network with the minimum number of reticulations, if one exists, in polynomial time. © 2009 Springer Berlin Heidelberg."
|
|
|
  
Philippe Gambette,
Vincent Berry and
Christophe Paul. The structure of level-k phylogenetic networks. In CPM09, Vol. 5577:289-300 of LNCS, springer, 2009. Keywords: coalescent, explicit network, galled tree, level k phylogenetic network, phylogenetic network, Program Recodon. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00371485/en/.
Toggle abstract
"Evolution is usually described as a phylogenetic tree, but due to some exchange of genetic material, it can be represented as a phylogenetic network which has an underlying tree structure. The notion of level was recently introduced as a parameter on realistic kinds of phylogenetic networks to express their complexity and tree-likeness. We study the structure of level-k networks, and how they can be decomposed into level-k generators. We also provide a polynomial time algorithm which takes as input the set of level-k generators and builds the set of level-(k + 1) generators. Finally, with a simulation study, we evaluate the proportion of level-k phylogenetic networks among networks generated according to the coalescent model with recombination. © 2009 Springer Berlin Heidelberg."
|
|
|
    
Daniel H. Huson,
Regula Rupp,
Vincent Berry,
Philippe Gambette and
Christophe Paul. Computing Galled Networks from Real Data. In ISMBECCB09, Vol. 25(12):i85-i93 of BIO, 2009. Keywords: abstract network, cluster containment, explicit network, FPT, from clusters, from rooted trees, galled network, NP complete, phylogenetic network, phylogeny, polynomial, Program Dendroscope, reconstruction. Note: http://hal-lirmm.ccsd.cnrs.fr/lirmm-00368545/en/.
Toggle abstract
"Motivation: Developing methods for computing phylogenetic networks from biological data is an important problem posed by molecular evolution and much work is currently being undertaken in this area. Although promising approaches exist, there are no tools available that biologists could easily and routinely use to compute rooted phylogenetic networks on real datasets containing tens or hundreds of taxa. Biologists are interested in clades, i.e. groups of monophyletic taxa, and these are usually represented by clusters in a rooted phylogenetic tree. The problem of computing an optimal rooted phylogenetic network from a set of clusters, is hard, in general. Indeed, even the problem of just determining whether a given network contains a given cluster is hard. Hence, some researchers have focused on topologically restricted classes of networks, such as galled trees and level-k networks, that are more tractable, but have the practical draw-back that a given set of clusters will usually not possess such a representation. Results: In this article, we argue that galled networks (a generalization of galled trees) provide a good trade-off between level of generality and tractability. Any set of clusters can be represented by some galled network and the question whether a cluster is contained in such a network is easy to solve. Although the computation of an optimal galled network involves successively solving instances of two different NP-complete problems, in practice our algorithm solves this problem exactly on large datasets containing hundreds of taxa and many reticulations in seconds, as illustrated by a dataset containing 279 prokaryotes. © 2009 The Author(s)."
|
|
|
     
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."
|
|
|

Chen Meng and
Laura S. Kubatko. Detecting hybrid speciation in the presence of incomplete lineage sorting using gene tree incongruence: A model. In Theoretical Population Biology, Vol. 75(1):35-45, 2009. Keywords: bayesian, coalescent, from network, from rooted trees, hybridization, likelihood, lineage sorting, phylogenetic network, phylogeny, statistical model. Note: http://dx.doi.org/10.1016/j.tpb.2008.10.004.
Toggle abstract
"The application of phylogenetic inference methods, to data for a set of independent genes sampled randomly throughout the genome, often results in substantial incongruence in the single-gene phylogenetic estimates. Among the processes known to produce discord between single-gene phylogenies, two of the best studied in a phylogenetic context are hybridization and incomplete lineage sorting. Much recent attention has focused on the development of methods for estimating species phylogenies in the presence of incomplete lineage sorting, but phylogenetic models that allow for hybridization have been more limited. Here we propose a model that allows incongruence in single-gene phylogenies to be due to both hybridization and incomplete lineage sorting, with the goal of determining the contribution of hybridization to observed gene tree incongruence in the presence of incomplete lineage sorting. Using our model, we propose methods for estimating the extent of the role of hybridization in both a likelihood and a Bayesian framework. The performance of our methods is examined using both simulated and empirical data. © 2008 Elsevier Inc. All rights reserved."
|
|
|
|
|
 
Chris Whidden and
Norbert Zeh. A Unifying View on Approximation and FPT of Agreement Forests. In WABI09, Vol. 5724:390-402 of LNCS, Springer, 2009. Keywords: agreement forest, approximation, explicit network, FPT, minimum number, phylogenetic network, phylogeny, reconstruction. Note: https://www.cs.dal.ca/sites/default/files/technical_reports/CS-2009-02.pdf.
Toggle abstract
"We provide a unifying view on the structure of maximum (acyclic) agreement forests of rooted and unrooted phylogenies. This enables us to obtain linear- or O(n log n)-time 3-approximation and improved fixed-parameter algorithms for the subtree prune and regraft distance between two rooted phylogenies, the tree bisection and reconnection distance between two unrooted phylogenies, and the hybridization number of two rooted phylogenies. © 2009 Springer Berlin Heidelberg."
|
|
|
     
Leo van Iersel,
Judith Keijsper,
Steven Kelk,
Leen Stougie,
Ferry Hagen and
Teun Boekhout. Constructing level-2 phylogenetic networks from triplets. In RECOMB08, Vol. 4955:450-462 of LNCS, springer, 2008. Keywords: explicit network, from triplets, level k phylogenetic network, NP complete, phylogenetic network, phylogeny, polynomial, Program Level2, reconstruction. Note: http://homepages.cwi.nl/~iersel/level2full.pdf. An appendix with proofs can be found here http://arxiv.org/abs/0707.2890.
Toggle abstract
"Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so, to construct such a network [24]. Here, we extend this work by showing that this problem is even polynomial time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontree-like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data. © 2009 IEEE."
|
|
|
  
Rune Lyngsø,
Yun S. Song and
Jotun Hein. Accurate Computation of Likelihoods in the Coalescent with Recombination via Parsimony. In RECOMB08, Vol. 4955:463-477 of LNCS, springer, 2008. Keywords: coalescent, likelihood, phylogenetic network, phylogeny, recombination, statistical model. Note: http://dx.doi.org/10.1007/978-3-540-78839-3_41.
Toggle abstract
"Understanding the variation of recombination rates across a given genome is crucial for disease gene mapping and for detecting signatures of selection, to name just a couple of applications. A widely-used method of estimating recombination rates is the maximum likelihood approach, and the problem of accurately computing likelihoods in the coalescent with recombination has received much attention in the past. A variety of sampling and approximation methods have been proposed, but no single method seems to perform consistently better than the rest, and there still is great value in developing better statistical methods for accurately computing likelihoods. So far, with the exception of some two-locus models, it has remained unknown how the true likelihood exactly behaves as a function of model parameters, or how close estimated likelihoods are to the true likelihood. In this paper, we develop a deterministic, parsimony-based method of accurately computing the likelihood for multi-locus input data of moderate size. We first find the set of all ancestral configurations (ACs) that occur in evolutionary histories with at most k crossover recombinations. Then, we compute the likelihood by summing over all evolutionary histories that can be constructed only using the ACs in that set. We allow for an arbitrary number of crossing over, coalescent and mutation events in a history, as long as the transitions stay within that restricted set of ACs. For given parameter values, by gradually increasing the bound k until the likelihood stabilizes, we can obtain an accurate estimate of the likelihood. At least for moderate crossover rates, the algorithm-based method described here opens up a new window of opportunities for testing and fine-tuning statistical methods for computing likelihoods. © 2008 Springer-Verlag Berlin Heidelberg."
|
|
|
 
Leo van Iersel and
Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets. In ISAAC08, Vol. 5369:472-483 of LNCS, springer, 2008. Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, minimum number, phylogenetic network, phylogeny, polynomial, Program Marlon, Program Simplistic. Note: http://arxiv.org/abs/0805.1859.
|
|
|
 
Cuong Than and
Luay Nakhleh. SPR-based Tree Reconciliation: Non-binary Trees and Multiple Solutions. In APBC08, Pages 251-260, 2008. Keywords: evaluation, from rooted trees, lateral gene transfer, phylogenetic network, phylogeny, Program LatTrans, Program PhyloNet, reconstruction, SPR distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/apbc08.pdf.
|
|
|
 
Lichen Bao and
Sergey Bereg. Clustered SplitsNetworks. In COCOA08, Vol. 5165:469-478 of LNCS, springer, 2008. Keywords: abstract network, from distances, NeighborNet, realization, reconstruction. Note: http://dx.doi.org/10.1007/978-3-540-85097-7_44, slides available at http://www.utdallas.edu/~besp/cocoa08talk.pdf.
Toggle abstract
"We address the problem of constructing phylogenetic networks using two criteria: the number of cycles and the fit value of the network. Traditionally the fit value is the main objective for evaluating phylogenetic networks. However, a small number of cycles in a network is desired and pointed out in several publications. We propose a new phylogenetic network called CS-network and a method for constructing it. The method is based on the well-known splitstree method. A CS-network contains a face which is k-cycle, k ≥ 3 (not as splitstree). We discuss difficulties of using non-parallelogram faces in splitstree networks. Our method involves clustering and optimization of weights of the network edges. The algorithm for constructing the underlying graph (except the optimization step) has a polynomial time. Experimental results show a good performance of our algorithm. © Springer-Verlag Berlin Heidelberg 2008."
|
|
|
|
|
 
Sagi Snir and
Tamir Tuller. Novel Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models. In WABI08, Vol. 5251:354-368 of LNCS, springer, 2008. Keywords: explicit network, from sequences, HMM, lateral gene transfer, likelihood, phylogenetic network, phylogeny, statistical model. Note: http://dx.doi.org/10.1007/978-3-540-87361-7_30.
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 for analyzing and modeling phylogenetic networks, the NET-HMM. 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 data set. 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 two different biological inputs. © 2008 Springer-Verlag Berlin Heidelberg."
|
|
|
   
Stefan Grünewald,
Andreas Spillner,
Kristoffer Forslund and
Vincent Moulton. Constructing Phylogenetic Supernetworks from Quartets. In WABI08, Vol. 5251:284-295 of LNCS, springer, 2008. Keywords: abstract network, from quartets, from unrooted trees, phylogenetic network, phylogeny, Program QNet, Program SplitsTree, reconstruction, split network. Note: http://dx.doi.org/10.1007/978-3-540-87361-7_24.
Toggle abstract
"In phylogenetics it is common practice to summarize collections of partial phylogenetic trees in the form of supertrees. Recently it has been proposed to construct phylogenetic supernetworks as an alternative to supertrees as these allow the representation of conflicting information in the trees, information that may not be representable in a single tree. Here we introduce SuperQ, a new method for constructing such supernetworks. It works by breaking the input trees into quartet trees, and stitching together the resulting set to form a network. The stitching process is performed using an adaptation of the QNet method for phylogenetic network reconstruction. In addition to presenting the new method, we illustrate the applicability of SuperQ to three data sets and discuss future directions for testing and development. © 2008 Springer-Verlag Berlin Heidelberg."
|
|
|
   
Gabriel Cardona,
Mercè Llabrés,
Francesc Rosselló and
Gabriel Valiente. Phylogenetic Networks: Justification, Models, Distances and Algorithms. In VI Jornadas de Matemática Discreta y Algorítmica (JMDA'08), 2008. Keywords: distance between networks, mu distance, phylogenetic network, phylogeny, polynomial, survey, time consistent network, tree-child network, tripartition distance, triplet distance. Note: http://bioinfo.uib.es/media/uploaded/jmda2008_submission_61-1.pdf.
|
|
|
 
Ernst Althaus and
Rouven Naujoks. Reconstructing Phylogenetic Networks with One Recombination. In Proceedings of the seventh International Workshop on Experimental Algorithms (WEA'08), Vol. 5038:275-288 of LNCS, springer, 2008. Keywords: enumeration, explicit network, exponential algorithm, from sequences, generation, parsimony, phylogenetic network, phylogeny, reconstruction, unicyclic network. Note: http://dx.doi.org/10.1007/978-3-540-68552-4_21.
Toggle abstract
"In this paper we propose a new method for reconstructing phylogenetic networks under the assumption that recombination events have occurred rarely. For a fixed number of recombinations, we give a generalization of the maximum parsimony criterion. Furthermore, we describe an exact algorithm for one recombination event and show that in this case our method is not only able to identify the recombined sequence but also to reliably reconstruct the complete evolutionary history. © 2008 Springer-Verlag Berlin Heidelberg."
|
|
|
  
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.
|
|
|
  
Cuong Than,
Guohua Jin and
Luay Nakhleh. Integrating Sequence and Topology for Efficient and Accurate Detection of Horizontal Gene Transfer. In Proceedings of the Sixth RECOMB Comparative Genomics Satellite Workshop (RECOMB-CG'08), Vol. 5267:113-127 of LNCS, springer, 2008. Keywords: bootstrap, explicit network, from rooted trees, from sequences, lateral gene transfer, phylogenetic network, phylogeny, Program Nepal, Program PhyloNet, reconstruction. Note: http://www.cs.rice.edu/~nakhleh/Papers/recombcg-08.pdf, slides available at http://igm.univ-mlv.fr/RCG08/RCG08slides/Cuong_Than_RCG08.pdf.
|
|
|
 
Daniel H. Huson and
Tobias Kloepper. Beyond Galled Trees - Decomposition and Computation of Galled Networks. In RECOMB07, Vol. 4453:211-225 of LNCS, springer, 2007. Keywords: FPT, from splits, from trees, galled network, phylogenetic network, phylogeny, Program SplitsTree, reconstruction. Note: http://dx.doi.org/10.1007/978-3-540-71681-5_15, errata..
|
|
|
|
|
|
|
|
|
|
|
 
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."
|
|
|
|
|
|
|
  
Hadas Birin,
Zohar Gal-Or,
Isaac Elias and
Tamir Tuller. Inferring Models of Rearrangements, Recombinations, and Horizontal Transfers by the Minimum Evolution Criterion. In WABI07, Vol. 4645:111-123 of LNCS, springer, 2007. Keywords: explicit network, from sequences, phylogenetic network, phylogeny, reconstruction. Note: http://safrabio.cs.tau.ac.il/download/Papers/Birin_et_al.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. 1 comment 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.
|
|
|
|
|
 
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.
|
|
|
 
Sergey Bereg and
Yuanyi Zhang. Phylogenetic Networks Based on the Molecular Clock Hypothesis. In BIBE05, Pages 320-323, 2005. Note: http://dx.doi.org/10.1109/BIBE.2005.46.
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 design an efficient algorithm for a special class of phylogenetic networks that can detect the existence of a network and constructs it. © 2005 IEEE.
|
|
|
|
|

Elena Dubrova. Phylogenetic networks with edge-disjoint recombination cycles. In Proceedings of SPIE Bioengineered and Bioinspired Systems II (SPIE-BBS II), Vol. 5839:381-388, 2005. Keywords: galled tree, phylogenetic network, polynomial, site consistency. Note: http://dx.doi.org/10.1117/12.607910.
Toggle abstract
"Phylogenetic analysis is a branch of biology that establishes the evolutionary relationships between living organisms. The goal of phylogenetic analysis is to determine the order and approximate timing of speciation events in the evolution of a given set of species. Phylogenetic networks allow to represent evolutionary histories that include events like recombination and hybridization. In this paper, we introduce a class of phylogenetic networks called extended galled-trees in which recombination cycles share no edge. We show that the site consistency problem, which is NP-hard in general, can be solved in polynomial time for this class of phylogenetic networks."
|
|
|
|
|
   
Trinh N. D. Huynh,
Jesper Jansson,
Nguyen Bao Nguyen and
Wing-Kin Sung. Constructing a Smallest Refining Galled Phylogenetic Network. In RECOMB05, Vol. 3500:265-280 of LNCS, springer, 2005. Keywords: from rooted trees, galled tree, NP complete, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction. Note: http://www.df.lth.se/~jj/Publications/refining_gn3_RECOMB2005.pdf.
|
|
|
   
Daniel H. Huson,
Tobias Kloepper,
Peter J. Lockhart and
Mike Steel. Reconstruction of Reticulate Networks from Gene Trees. In RECOMB05, Vol. 3500:233-249 of LNCS, springer, 2005. Keywords: from rooted trees, from splits, phylogenetic network, phylogeny, reconstruction, split, split network, visualization. Note: http://dx.doi.org/10.1007/11415770_18.
|
|
|
 
Daniel H. Huson and
Tobias Kloepper. Computing recombination networks from binary sequences. In ECCB05, Vol. 21(suppl. 2):ii159-ii165 of BIO, 2005. Keywords: from sequences, phylogenetic network, phylogeny, recombination. Note: http://dx.doi.org/10.1093/bioinformatics/bti1126.
Toggle abstract
"Motivation:Phylogenetic networks are becoming an important tool in molecular evolution, as the evolutionary role of reticulate events, such as hybridization, horizontal gene transfer and recombination, is becoming more evident, and as the available data is dramatically increasing in quantity and quality. Results: This paper addresses the problem of computing a most parsimonious recombination network for an alignment of binary sequences that are assumed to have arisen under the 'infinite sites' model of evolution with recombinations. Using the concept of a splits network as the underlying datastructure, this paper shows how a recent method designed for the computation of hybridization networks can be extended to also compute recombination networks. A robust implementation of the approach is provided and is illustrated using a number of real biological datasets. © The Author 2005. Published by Oxford University Press. All rights reserved."
|
|
|
|
|
  
Jesper Jansson,
Nguyen Bao Nguyen and
Wing-Kin Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. In SODA05, Pages 349-358, 2005. 1 comment Keywords: approximation, explicit network, from triplets, galled tree, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://portal.acm.org/citation.cfm?id=1070481.
|
|
|
  
Rune Lyngsø,
Yun S. Song and
Jotun Hein. Minimum Recombination Histories by Branch and Bound. In WABI05, Vol. 3692:239-250 of LNCS, springer, 2005. Keywords: ARG, branch and bound, from sequences, minimum number, Program Beagle, recombination, reconstruction, software. Note: http://www.cs.ucdavis.edu/~yssong/Pub/WABI05-239.pdf.
|
|
|

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.
|
|
|
 
Luay Nakhleh and
Li-San Wang. Phylogenetic Networks, Trees, and Clusters. In IWBRA05, Vol. 3515:919-926 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/NakhlehWang.pdf.
|
|
|
 
Luay Nakhleh and
Li-San Wang. Phylogenetic Networks: Properties and Relationship to Trees and Clusters. In TCSB2, Vol. 3680:82-99 of LNCS, springer, 2005. Keywords: cluster containment, evaluation, from clusters, from network, from rooted trees, phylogenetic network, phylogeny, polynomial, tree containment, tree-child network. Note: http://www.cs.rice.edu/~nakhleh/Papers/LNCS_TCSB05.pdf.
|
|
|
|
|
|
|
|
|
  
Yun S. Song,
Yufeng Wu and
Dan Gusfield. Efficient computation of close lower and upper bounds on the minimum number of recombinations in biological sequence evolution. In ISMB05, Vol. 21:i413-i422 of BIO, 2005. Keywords: integer linear programming, minimum number, Program HapBound, Program SHRUB, recombination. Note: http://dx.doi.org/10.1093/bioinformatics/bti1033.
Toggle abstract
"Motivation: We are interested in studying the evolution of DNA single nucleotide polymorphism sequences which have undergone (meiotic) recombination. For a given set of sequences, computing the minimum number of recombinations needed to explain the sequences (with one mutation per site) is a standard question of interest, but it has been shown to be NP-hard, and previous algorithms that compute it exactly work either only on very small datasets or on problems with special structure. Results: In this paper, we present efficient, practical methods for computing both upper and lower bounds on the minimum number of needed recombinations, and for constructing evolutionary histories that explain the input sequences. We study in detail the efficiency and accuracy of these algorithms on both simulated and real data sets. The algorithms produce very close upper and lower bounds, which match exactly in a surprisingly wide range of data. Thus, with the use of new, very effective lower bounding methods and an efficient algorithm for computing upper bounds, this approach allows the efficient, exact computation of the minimum number of needed recombinations, with high frequency in a large range of data. When upper and lower bounds match, evolutionary histories found by our algorithm correspond to the most parsimonious histories. © The Author 2005. Published by Oxford University Press. All rights reserved."
|
|
|
|
|
 
Jesper Jansson and
Wing-Kin Sung. Inferring a level-1 phylogenetic network from a dense set of rooted triplets. In COCOON04, Vol. 3106:462-471 of LNCS, springer, 2004. 1 comment Keywords: explicit network, from triplets, galled tree, level k phylogenetic network, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.df.lth.se/~jj/Publications/ipnrt6_COCOON2004.pdf.
|
|
|
  
Luay Nakhleh,
Tandy Warnow and
C. Randal Linder. Reconstructing reticulate evolution in species - theory and practice. In RECOMB04, Pages 337-346, 2004. Keywords: from rooted trees, galled tree, phylogenetic network, phylogeny, polynomial, Program SPNet, reconstruction, software. Note: http://www.cs.rice.edu/~nakhleh/Papers/144-nakhleh.pdf.
|
|
|
  
Mike Hallett,
Jens Lagergren and
Ali Tofigh. Simultaneous Identification of Duplications and Lateral Transfers. In RECOMB04, Pages 347-356, 2004. Keywords: duplication, explicit network, FPT, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.nada.kth.se/~jensl/p164-hallett.pdf.
|
|
|

Pawel Górecki. Reconciliation problems for duplication, loss and horizontal gene transfer. In RECOMB04, Pages 316-325, 2004. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, loss, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://ai.stanford.edu/~serafim/CS374_2004/Papers/Gorecki_Reconciliation.pdf.
|
|
|
|
|
|
|
     
Luay Nakhleh,
Jerry Sun,
Tandy Warnow,
C. Randal Linder,
Bernard M. E. Moret and
Anna Tholse. Towards the Development of Computational Tools for Evaluating Phylogenetic Network Reconstruction Methods. In PSB03, 2003. Keywords: distance between networks, evaluation, phylogenetic network, phylogeny, polynomial, tripartition distance. Note: http://www.cs.rice.edu/~nakhleh/Papers/psb03.pdf.
|
|
|
|
|
|
|

Pawel Górecki. Single step reconciliation algorithm for duplication, loss and horizontal gene transfer model. In ECCB03, 2003. Keywords: duplication, explicit network, from rooted trees, from species tree, lateral gene transfer, NP complete, parsimony, phylogenetic network, phylogeny, polynomial, reconstruction. Note: http://www.inra.fr/eccb2003/posters/pdf/short/S_gorecki.ps.
|
|
|
 
David Bryant and
Vincent Moulton. Neighbor-Net: An Agglomerative Method for the Construction of Planar Phylogenetic Networks. In WABI02, Vol. 2452:375-391 of LNCS, springer, 2002. Keywords: abstract network, circular split system, from distances, NeighborNet, phylogenetic network, phylogeny, Program SplitsTree, reconstruction, split network. Note: http://dx.doi.org/10.1007/3-540-45784-4_28.
|
|
|
|
|
  
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."
|
|
|
|
|
|
|
  
Lusheng Wang,
Kaizhong Zhang and
Louxin Zhang. Perfect phylogenetic networks with recombination. In SAC01, Pages 46-50, 2001. Keywords: from sequences, galled tree, NP complete, perfect, phylogenetic network, phylogeny, polynomial, recombination, reconstruction. Note: http://dx.doi.org/10.1145/372202.372271.
|
|
|
|
|
|
|

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."
|
|
|
 
Vincent Berry and
David Bryant. Faster reliable phylogenetic analysis. In RECOMB99, Pages 59-68, 1999. Keywords: abstract network, from quartets, phylogenetic network, phylogeny, polynomial, Program SplitsTree, reconstruction, split network, weakly compatible. Note: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.9151.
|
|
|
  
Bin Ma,
Lusheng Wang and
Ming Li. Fixed topology alignment with recombination. In CPM98, Vol. 1448:174-188 of LNCS, springer, 1998. Keywords: approximation, explicit network, from network, from sequences, galled tree, inapproximability, phylogenetic network, phylogeny, recombination. Note: http://dx.doi.org/10.1007/BFb0030789.
|
|
|
|
|
|
|

Hans-Jürgen Bandelt. Phylogenetic Networks. In Verhandlungen des Naturwissenschaftlichen Vereins Hamburg, Vol. 34:51-71, 1994.
|
|
|
|
|

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