26 papers · ranked by Valyu relevance
Jie Zhang, En‐hui Yang, John C. Kieffer
We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a…
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…
Matthew J Penn, Neil Scheidwasser, Mark P Khurana, David A Duchêne + 3 more
'Christl A Donnelly' 'Samir Bhatt' 'Stephen Smith'] Title: Abstract Binary phylogenetic trees inferred from biological data are central to understanding the shared history among evolutionary units. However, inferring the placement of latent nodes in a tree is computationally expensive. State-of-the-art methods rely on…
Kou Hamada, Sankardeep Chakraborty, Seungbum Jo, Takuto Koriyama + 2 more
and Efficient Implementation of Average-Case Optimal RMQs Authors: ['Kou Hamada' 'Sankardeep Chakraborty' 'Seungbum Jo' 'Takuto Koriyama' 'Kunihiko Sadakane' 'Srinivasa Rao Satti'] Tree covering is a technique for decomposing a tree into smaller-sized trees with desirable properties, and has been employed in various…
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…
Xi He, Max A. Little
In this paper, we introduce a generic data structure called decision trees, which integrates several well-known data structures, including binary search trees, -D trees, binary space partition trees, and decision tree models from machine learning. We provide the first axiomatic definition of decision trees. These…
Svante Janson
We study the distribution of fringe trees in Patricia tries and compressed binary search trees; both cases are random binary trees that have been compressed by deleting vertices of outdegree 1 so that they are random full binary trees. The main results are central limit theorems for the number of fringe trees of a…
Hadi Poormohammadi, Mohsen Sardari Zarchi, Hocine Cherifi
Phylogenetic networks construction is one the most important challenge in phylogenetics. These networks can present complex non-treelike events such as gene flow, horizontal gene transfers, recombination or hybridizations. Among phylogenetic networks, rooted structures are commonly used to represent the evolutionary…
Hadi Poormohammadi, Mohsen Sardari Zarchi
Phylogenetic networks construction is one the most important challenge in phylogenetics. These networks can present complex non-treelike events such as gene flow, horizontal gene transfers, recombination or hybridizations. Among phylogenetic networks, rooted structures are commonly used to represent the evolutionary…
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…
Michael Goodrich, Yan Gu, Ryuto Kitagawa, Yihan Sun
Balanced search trees are widely used in computer science to efficiently maintain dynamic ordered data. To support efficient set operations (e.g., union, intersection, difference) using trees, the join-based framework is widely studied. This framework has received particular attention in the parallel setting, and has…
Chen Avin
Motivated by recent developments in optical switching and reconfigurable network design, we study dynamic binary search trees (BSTs) in the matching model. In the classical dynamic BST model, the cost of both link traversal and basic reconfiguration (rotation) is O(1). However, in the matching model, the BST is defined…
Raazesh Sainudiin, Amandine Véber
In this article, we construct a generalization of the Blum-François Beta-splitting model for evolutionary trees, which was itself inspired by Aldous' Beta-splitting model on cladograms. The novelty of our approach allows for asymmetric shares of diversification rates (or diversification ‘potential’) between two sister…
Edwin Jacox, Mathias Weller, Eric Tannier, Celine Scornavacca
Gene trees reconstructed from sequence alignments contain poorly supported branches when the phylogenetic signal in the sequences is weak. When a species tree is available, the signal of gains and losses of genes can be used to correctly resolve the unsupported parts of the gene history. Unfortunately, finding the best…
István Finta, Sándor Szénási, Lóránt Farkas
In this contribution, we provide a detailed analysis of the search operation for the Interval Merging Binary Tree (IMBT), an efficient data structure proposed earlier to handle typical anomalies in the transmission of data packets. A framework is provided to decide under which conditions IMBT outperforms other data…
Manuel Lafond, Aïda Ouangraoua, Nadia El-Mabrouk
Combining a set of trees on partial datasets into a single tree is a classical method for inferring large phylogenetic trees. Ideally, the combined tree should display each input partial tree, which is only possible if input trees do not contain contradictory phylogenetic information. The simplest version of the…
Heng Li, Jiazhen Rong
We present bedtk, a new toolkit for manipulating genomic intervals in the BED format. It supports sorting, merging, intersection, subtraction and the calculation of the breadth of coverage. Bedtk employs implicit interval tree, a new data structure for fast interval overlap queries. It is several to tens of times…
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…
Axel Trefzer, Alexandros Stamatakis
Bayesian Markov-Chain Monte Carlo (MCMC) methods for phylogenetic tree inference, that is, inference of the evolutionary history of distinct species using their molecular sequence data, typically generate large sets of phylogenetic trees. The trees generated by the MCMC procedure are samples of the posterior…
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…
Jingyi Liu, Ross Mawhorter, Nuo Liu, Santi Santichaivekin + 2 more
Analyses of microbial evolution often use reconciliation methods. However, the standard duplication-transfer-loss (DTL) model does not account for the fact that species trees are often not fully sampled and thus, from the perspective of reconciliation, a gene family may enter the species tree from the outside.…
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…
Leonid Zaslavsky, Yiming Bao, Tatiana A Tatusova
Background With the amount of influenza genome sequence data growing rapidly, researchers need machine assistance in selecting datasets and exploring the data. Enhanced visualization tools are required to represent results of the exploratory analysis on the web in an easy-to-comprehend form and to facilitate convenient…
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…
Camila Zanette, Caitlin C. Bannan, Christopher I. Bayly, Josh Fass + 4 more
Molecular mechanics force fields define how the energy and forces of a molecular system are computed from its atomic positions, and enable the study of such systems through computational methods like molecular dynamics and Monte Carlo simulations. Despite progress toward automated force field parameterization…
Grzegorz Skoraczyński, Mateusz Kitlas, Błażej Miasojedow, Anna Gambin
Modern computer-assisted synthesis planning tools provide strong support for this problem. However, they are still limited by computational complexity. This limitation may be overcome by scoring the synthetic accessibility as a pre-retrosynthesis heuristic. A wide range of machine learning scoring approaches is…