15 papers · ranked by Valyu relevance
Jerome Kelleher, Kevin R. Thornton, Jaime Ashander, Peter L. Ralph + 1 more
In this paper we describe how to efficiently record the entire genetic history of a population in forwards-time, individual-based population genetics simulations with arbitrary breeding models, population structure and demography. This approach dramatically reduces the computational burden of tracking individual…
Cheng-Yuan Liou, Shen-Han Tseng, Wei-Chen Cheng, Huai-Ying Tsai
In modern bioinformatics, finding an efficient way to allocate sequence fragments with biological functions is an important issue. This paper presents a structural approach based on context-free grammars extracted from original DNA or protein sequences. This approach is radically different from all those statistical…
Julia A. Palacios, Anand Bhaskar, Filippo Disanto, Noah A. Rosenberg
Evolutionary models used for describing molecular sequence variation suppose that at a non-recombining genomic segment, sequences share ancestry that can be represented as a genealogy-a rooted, binary, timed tree, with tips corresponding to individual sequences. Under the infinitely-many-sites mutation model, mutations…
Katharina T. Huber, Simone Linz, Vincent Moulton
Recently there has been considerable interest in the problem of finding a phylogenetic network with a minimum number of reticulation vertices which displays a given set of phylogenetic trees, that is, a network with minimum hybrid number. Such networks are useful for representing the evolution of species whose genomes…
Fabian Sievers, Graham M Hughes, Desmond G Higgins
Background Guide-trees are used as part of an essential heuristic to enable the calculation of multiple sequence alignments. They have been the focus of much method development but there has been little effort at determining systematically, which guide-trees, if any, give the best alignments. Some guide-tree…
T. Flouri, K. Kobert, S. P. Pissis, A. Stamatakis
Given a labelled tree T, our goal is to group repeating subtrees of T into equivalence classes with respect to their topologies and the node labels. We present an explicit, simple and time-optimal algorithm for solving this problem for unrooted unordered labelled trees and show that the running time of our method is…
Alexandra Gavryushkina, David Welch, Alexei J Drummond
Background In Bayesian phylogenetic inference we are interested in distributions over a space of trees. The number of trees in a tree space is an important characteristic of the space and is useful for specifying prior distributions. When all samples come from the same time point and no prior information available on…
Michael Drmota, Emma Yu Jin, Benedikt Stufler
For any set Ω of non-negative integers such that , we consider a random Ω-k-tree Gn,k that is uniformly selected from all connected k-trees of (n + k) vertices such that the number of (k + 1)-cliques that contain any fixed k-clique belongs to Ω. We prove that Gn,k, scaled by where Hk is the kth harmonic number and σΩ >…
Shaili Mathur, Noah A. Rosenberg
Objective In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we…
Luc Devroye, Michael R. Doboli, Noah A. Rosenberg, Stephan Wagner
The Colijn-Plazzotta ranking is a bijective encoding of the unlabeled binary rooted trees with positive integers. We show that the rank f(t) of a tree t is closely related to its height h, the maximal path length from a leaf to the root. We consider the rank $f\tau _n$ of a random n-leaf tree $\tau _n$ under each of…
Tomás M. Coronado, Arnau Mir, Francesc Rosselló, Lucía Rotger
Background The Sackin index*S* of a rooted phylogenetic tree, defined as the sum of its leaves’ depths, is one of the most popular balance indices in phylogenetics, and Sackin’s paper (Syst Zool 21:225-6, 1972) is usually cited as the source for this index. However, what Sackin actually proposed in his paper as a…
François Bienvenu, Mike Steel
In a recent paper, the question of determining the fraction of binary trees that contain a fixed pattern known as the snowflake was posed. We show that this fraction goes to 1, providing two very different proofs: a purely combinatorial one that is quantitative and specific to this problem; and a proof using branching…
Nahla A. Belal, Lenwood S. Heath, Vladimir Makarenkov
We present a method for detecting horizontal gene transfer (HGT) using partial orders (posets). The method requires a poset for each species/gene pair, where we have a set of species S, and a set of genes G. Given the posets, the method constructs a phylogenetic tree that is compatible with the set of posets; this is…
Katharina Jahn, Niko Beerenwinkel, Louxin Zhang
Background Mutation trees are rooted trees in which nodes are of arbitrary degree and labeled with a mutation set. These trees, also referred to as clonal trees, are used in computational oncology to represent the mutational history of tumours. Classical tree metrics such as the popular Robinson-Foulds distance are of…
Andreas Sand, Morten K. Holt, Jens Johansen, Rolf Fagerberg + 3 more
'Gerth Stølting Brodal' 'Christian N. S. Pedersen' 'Thomas Mailund'] Distance measures between trees are useful for comparing trees in a systematic manner, and several different distance measures have been proposed. The triplet and quartet distances, for rooted and unrooted trees, respectively, are defined as the…