Dec 6, 2014

Neighborhoods of trees in circular orderings

Bulletin of Mathematical Biology
Sarah BastkowskiTaoyang Wu


In phylogenetics, a common strategy used to construct an evolutionary tree for a set of species [Formula: see text] is to search in the space of all such trees for one that optimizes some given score function (such as the minimum evolution, parsimony or likelihood score). As this can be computationally intensive, it was recently proposed to restrict such searches to the set of all those trees that are compatible with some circular ordering of the set [Formula: see text]. To inform the design of efficient algorithms to perform such searches, it is therefore of interest to find bounds for the number of trees compatible with a fixed ordering in the neighborhood of a tree that is determined by certain tree operations commonly used to search for trees: the nearest neighbor interchange (NNI), the subtree prune and regraft (SPR) and the tree bisection and reconnection (TBR) operations. We show that the size of such a neighborhood of a binary tree associated with the NNI operation is independent of the tree's topology, but that this is not the case for the SPR and TBR operations. We also give tight upper and lower bounds for the size of the neighborhood of a binary tree for the SPR and TBR operations and characterize those trees for wh...Continue Reading

  • References10
  • Citations


  • References10
  • Citations


  • This paper may not have been cited yet.

Mentioned in this Paper

Likelihood Functions
PRUNE gene
Mathematical Concepts
Evolution, Molecular
Anatomy, Regional

Trending Feeds


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

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Adrien GoëffonJin-Kao Hao
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Magnus BordewichVincent Moulton
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Peter J Humphries, Taoyang Wu
© 2020 Meta ULC. All rights reserved