Aug 2, 2017

The combinatorics of discrete time-trees: theory and open problems

Journal of Mathematical Biology
Alex GavryushkinFrederick A Matsen

Abstract

A time-tree is a rooted phylogenetic tree such that all internal nodes are equipped with absolute divergence dates and all leaf nodes are equipped with sampling dates. Such time-trees have become a central object of study in phylogenetics but little is known about the parameter space of such objects. Here we introduce and study a hierarchy of discrete approximations of the space of time-trees from the graph-theoretic and algorithmic point of view. One of the basic and widely used phylogenetic graphs, the [Formula: see text] graph, is the roughest approximation and bottom level of our hierarchy. More refined approximations discretize the relative timing of evolutionary divergence and sampling dates. We study basic graph-theoretic questions for these graphs, including the size of neighborhoods, diameter upper and lower bounds, and the problem of finding shortest paths. We settle many of these questions by extending the concept of graph grammars introduced by Sleator, Tarjan, and Thurston to our graphs. Although time values greatly increase the number of possible trees, we show that 1-neighborhood sizes remain linear, allowing for efficient local exploration and construction of these graphs. We also obtain upper bounds on the r-ne...Continue Reading

  • References20
  • Citations2

Citations

Mentioned in this Paper

Study
Size
Bounded by
Trees (plant)
Phylogenetic Analysis
Theoretical Study
Anatomical Space Structure
Evaluation
Mathematical Formula
Local

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Bone Marrow Neoplasms

Bone Marrow Neoplasms are cancers that occur in the bone marrow. Discover the latest research on Bone Marrow Neoplasms here.

IGA Glomerulonephritis

IgA glomerulonephritis is a chronic form of glomerulonephritis characterized by deposits of predominantly Iimmunoglobin A in the mesangial area. Discover the latest research on IgA glomerulonephritis here.

Cryogenic Electron Microscopy

Cryogenic electron microscopy (Cryo-EM) allows the determination of biological macromolecules and their assemblies at a near-atomic resolution. Here is the latest research.

STING Receptor Agonists

Stimulator of IFN genes (STING) are a group of transmembrane proteins that are involved in the induction of type I interferon that is important in the innate immune response. The stimulation of STING has been an active area of research in the treatment of cancer and infectious diseases. Here is the latest research on STING receptor agonists.

LRRK2 & Immunity During Infection

Mutations in the LRRK2 gene are a risk-factor for developing Parkinson’s disease. However, LRRK2 has been shown to function as a central regulator of vesicular trafficking, infection, immunity, and inflammation. Here is the latest research on the role of this kinase on immunity during infection.

Antiphospholipid Syndrome

Antiphospholipid syndrome or antiphospholipid antibody syndrome (APS or APLS), is an autoimmune, hypercoagulable state caused by the presence of antibodies directed against phospholipids.

Meningococcal Myelitis

Meningococcal myelitis is characterized by inflammation and myelin damage to the meninges and spinal cord. Discover the latest research on meningococcal myelitis here.

Alzheimer's Disease: MS4A

Variants within membrane-spanning 4-domains subfamily A (MS4A) gene cluster have recently been implicated in Alzheimer's disease by recent genome-wide association studies. Here is the latest research.

Related Papers

Bulletin of Mathematical Biology
Sarah BastkowskiTaoyang Wu
Bulletin of Mathematical Biology
P GambetteG E Scholz
Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
Dan GusfieldYun S Song
© 2020 Meta ULC. All rights reserved