25 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…
Fabrizio Luccio
We propose a new arithmetic for non-empty rooted unordered trees simply called trees. After discussing tree representation and enumeration, we define the operations of tree addition, multiplication and stretch, prove their properties, and show that all trees can be generated from a starting tree of one vertex. We then…
Paul H. Brown, Trevor Fenner
In this paper, we introduce a new representation for ordered trees, the weight sequence representation. We then use this to construct new representations for both rooted trees and free trees, namely the canonical weight sequence representation. We construct algorithms for generating the weight sequence representations…
Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti
We observe that a standard transformation between ordinal trees (arbitrary rooted trees with ordered children) and binary trees leads to interesting succinct binary tree representations. There are four symmetric versions of these transformations. Via these transformations we get four succinct representations of n-node…
Peter Ralph, Kevin Thornton, Jerome Kelleher
As a genetic mutation is passed down across generations, it distinguishes those genomes that have inherited it from those that have not, providing a glimpse of the genealogical tree relating the genomes to each other at that site. Statistical summaries of genetic variation therefore also describe the underlying…
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…
Michael Dairyko, Lara Pudwell, Samantha Tyner, Casey Wynn
In this paper we consider the enumeration of binary trees avoiding non-contiguous binary tree patterns. We begin by computing closed formulas for the number of trees avoiding a single binary tree pattern with 4 or fewer leaves and compare these results to analogous work for contiguous tree patterns. Next, we give an…
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…
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…
Lukas Hübner, Alexandros Stamatakis
The field of population genetics attempts to advance our understanding of evolutionary processes. It has applications, for example, in medical research, wildlife conservation, and – in conjunction with recent advances in ancient DNA sequencing technology – studying human migration patterns over the past few thousand…
Noah A. Rosenberg
Colijn & Plazzotta (Syst. Biol. 67:113-126, 2018) introduced a scheme for bijectively associating the unlabeled binary rooted trees with the positive integers. First, the rank 1 is associated with the 1-leaf tree. Proceeding recursively, ordered pair (k_1_, k_2_), k_1_ ⩾ k_2_ ⩾ 1, is then associated with the tree whose…
Helmut Prodinger
Hex-trees are identified as a particular instance of weighted unary-binary trees. The Horton-Strahler numbers of these objects are revisited, and, thanks to a substitution that is not immediately intuitive, explicit results are possible. They are augmented by asymptotic evaluations as well. Furthermore, marked ordered…
Markus Kuba, Alois Panholzer
For all tree classes we show characterizations of suitable generating functions for the tree enumeration sequence via differential equations. Furthermore, for several combinatorial classes of multilabelled increasing tree families we present explicit enumeration results. We also present multilabelled increasing 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…
Michael Wallner
Plane increasing trees are rooted labeled trees embedded into the plane such that the sequence of labels is increasing on any branch starting at the root. Relaxed binary trees are a subclass of unlabeled directed acyclic graphs. We construct a bijection between these two combinatorial objects and study the therefrom…
Jacob Gilbert, Chih Hao Wu, Marina Knittel, Alejandro A. Schäffer + 2 more
Understanding and comparing tumor evolutionary histories is fundamental to cancer genomics. Clonal trees, used to model tumor progression, are rooted, unordered trees in which each node represents a subclone labeled by a set of distinct mutations. To compare two clonal trees, we introduce omlta, the optimal multi-label…
Pengyu Liu, Matthew Gould, Caroline Colijn
Phylogenetic trees are a central tool in evolutionary biology. They demonstrate evolutionary patterns among species, genes, and with modern sequencing technologies, patterns of ancestry among sets of individuals. Phylogenetic trees usually consist of tree shapes, branch lengths and partial labels. Comparing tree shapes…
C. Colijn, G. Plazzotta
The shapes of evolutionary trees are influenced by the nature of the evolutionary process, but comparisons of trees from different processes are hindered by the challenge of completely describing tree shape. We present a full characterization of the shapes of rooted branching trees in a form that lends itself to…
Miklós Bóna
In a rooted tree, we call a vertex balanced if it is at equal distance from all its descendant leaves. We count balanced vertices in three different tree varieties. For decreasing binary trees, we can prove that the probability that a vertex chosen uniformly at random from the set of all trees of a given size is…
Authors not listed
RNA molecules fold into complex three-dimensional structures that determine their function. A wide range of mathematical frameworks, such as chord diagrams, fatgraphs, and context-free grammars, have been used to represent these structures; however, these models have largely been developed from mathematical motivations…
Vladimir Kondratyev, Marian Dryzhakov, Timur Gimadiev, Dmitriy Slutskiy
In this work, we provide further development of the junction tree variational autoencoder (JT VAE) architecture in terms of implementation and application of the internal feature space of the model. Pretraining of JT VAE on a large dataset and further optimization with a regression model led to a latent space that can…
Richard Apodaca
Despite its widespread use, Simplified Molecular Input Line Entry System (SMILES) remains underspecified. The lack of a detailed specification encourages improvisation by software developers, complicates data standardization efforts, and undermines extension development. Balsa, a reformulation of SMILES, addresses…
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…
Jonas Schaub, Julian Zander, Achim Zielesny, Christoph Steinbeck
The concept of molecular scaffolds as defining core structures of organic molecules is utilised in many areas of chemistry and cheminformatics, e.g. drug design, chemical classification, or the analysis of high-throughput screening data. Here, we present Scaffold Generator, a comprehensive open library for the…
Authors not listed
We present a simple yet efficient random (brute-force) algorithm for constructing solvated molecular systems. By placing solvent molecules at random positions and orientations within a simulation box, we circumvent the complexities typically associated with more sophisticated packing algorithms. The main computational…