Who is Who in Phylogenetic Networks

Publications of Sergey Bereg     Order by:   Type | Year
Associated keywords
abstract-network evaluation explicit-network from-distances from-splits NeighborNet phylogenetic-network phylogeny Program-PADRE Program-PhippsNetwork Program-SplitsTree Program-T-REX realization reconstruction software split split-network visualization
2012
1 Paul Phipps and Sergey Bereg. Optimizing Phylogenetic Networks for Circular Split Systems. In TCBB, Vol. 9(2):535-547, 2012. Keywords: abstract network, from distances, from splits, phylogenetic network, phylogeny, Program PhippsNetwork, reconstruction, software.         Toggle abstract "We address the problem of realizing a given distance matrix by a planar phylogenetic network with a minimum number of faces. With the help of the popular software SplitsTree4, we start by approximating the distance matrix with a distance metric that is a linear combination of circular splits. The main results of this paper are the necessary and sufficient conditions for the existence of a network with a single face. We show how such a network can be constructed, and we present a heuristic for constructing a network with few faces using the first algorithm as the base case. Experimental results on biological data show that this heuristic algorithm can produce phylogenetic networks with far fewer faces than the ones computed by SplitsTree4, without affecting the approximation of the distance matrix. © 2012 IEEE." 2 Ruogu Sheng and Sergey Bereg. Approximating Metrics with Planar Boundary-Labeled Phylogenetic Networks. In JBCB, Vol. 10(6):1250017, 2012. Keywords: abstract network, from distances, phylogenetic network, phylogeny, reconstruction.         Toggle abstract "Phylogenetic networks are useful for visualizing evolutionary relationships between species with reticulate events such as hybridizations and horizontal gene transfers. In this paper, we consider the problem of constructing undirected phylogenetic networks that (1) are planar graphs and (2) admit embeddings in the plane where the vertices labeling all taxa are on the boundary of the network. We develop a new algorithm for constructing phylogenetic networks satisfying these constraints. First, we show that only approximate networks can be constructed for some distance matrices with at least five taxa. Then we prove that any five-point metric can be represented approximately by a planar boundary-labeled network with guaranteed fit value of 94.79. We extend the networks constructed in the proof to design an algorithm for computing planar boundary-labeled networks for any number of taxa. © 2012 Imperial College Press."
2009
3 Lichen Bao and Sergey Bereg. Counting Faces in Split Networks. In ISBRA09, Vol. 5251:284-295 of LNCS, 2009. Note: http://dx.doi.org/10.1007/978-3-642-01551-9_12.         Toggle abstract SplitsTree is a popular program for inferring and visualizing various phylogenetic networks including split networks. Split networks are useful for realizing metrics that are linear combinations of split metrics. We show that the realization is not unique in some cases and design an algorithm for computing split networks with minimum number of faces. We also prove that the minimum number of faces in a split network is equal to the number of pairs of incompatible splits. 4 Poornima Venugopal and Sergey Bereg. Layout of Phylogenetic Networks and Multi-Labeled Trees. In BIOT'09, Pages 91, 2009. Keywords: explicit network, phylogenetic network, phylogeny, Program PADRE, visualization. Note: http://www.biotconf.org/PDFs/1456.pdf.
2008
5 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."
2007
6 Yuanyi Zhang, Lichen Bao and Sergey Bereg. Optimizing Split Networks. 2007. Note: UC Dallas Computer Science Technical Report UTDCS-08-07.
2006
7 Sergey Bereg and Yuanyi Zhang. Phylogenetic Networks Based on the Molecular Clock Hypothesis. In TCBB, Vol. 3(4), 2006. Note: http://www.utdallas.edu/~yzhang/Homepage/Papers/prep-tcbb.pdf.         Toggle abstract A classical result in phylogenetic trees is that a binary phylogenetic tree adhering to the molecular clock hypothesis exists if and only if the matrix of distances between taxa is ultrametric. The ultrametric condition is very restrictive. In this paper we study phylogenetic networks that can be constructed assuming the molecular clock hypothesis. We characterize distance matrices that admit such networks for 3 and 4 taxa. We also design two algorithms for constructing networks optimizing the least-squares fit.
2005
8 Sergey Bereg and Kathryn Bean. Constructing Phylogenetic Networks from Trees. In BIBE05, Pages 299-305, 2005. Keywords: evaluation, from distances, phylogenetic network, phylogeny, Program SplitsTree, Program T REX, reconstruction, split, split network. Note: http://dx.doi.org/10.1109/BIBE.2005.19.         Toggle abstract We present a new method of constructing a phylogenetic network from a given phylogenetic tree. It is based on a procedure that locally improves the tree. The procedure is quite general and can be applied to phylogenetic networks. By repeating local improvements user can introduce a given number of recombination cycles. A sequence of networks with decreasing distance deviation can be generated. The algorithm is efficient and shows a good performance on an example with plants. This is due to the fact that the update in every step is local and optimal. © 2005 IEEE. 9 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.