Balanced vertices in trees and a simpler algorithm to compute the genomic distance

DOI10.1016/J.AML.2010.08.021MaRDI QIDQ607155zbMATH OpenOpenAlexFDO

Authors Péter L. Erdős, Lajos Soukup, Jens Stoye

Publication date 19 November 2010

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.2735, http://real.mtak.hu/10111/1/ESS-arXiv1004.2735v1.pdf

zbMATH Keywords

genome rearrangementrooted treecomparative genomics

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75)

Abstract: This paper provides a short and transparent solution for the covering cost of white-grey trees which play a crucial role in the algorithm of Bergeron {it et al.} to compute the rearrangement distance between two multichromosomal genomes in linear time ({it Theor. Comput. Sci.}, 410:5300-5316, 2009). In the process it introduces a new {em center} notion for trees, which seems to be interesting on its own.

Recommendations

• Approximation algorithms for tree alignment with a given phylogeny
• A new balance index for phylogenetic trees
• On a matching distance between rooted phylogenetic trees
• scientific article; zbMATH DE number 2079368
• Computing the rooted triplet distance between phylogenetic networks
• Computing the rooted triplet distance between phylogenetic networks
• Aligning sequences via an evolutionary tree: complexity and approximation
• On distances in vertex-weighted trees
• On the complexity of computing MP distance between binary phylogenetic trees

Cites work

• scientific article; zbMATH DE number 1306890 (Why is no real title available?)
• scientific article; zbMATH DE number 3332242 (Why is no real title available?)
• A new linear time algorithm to compute the genomic distance via the double cut and join distance

Cited in

(2)

• A new linear time algorithm to compute the genomic distance via the double cut and join distance
• HP Distance Via Double Cut and Join Distance

This page was built for publication: Balanced vertices in trees and a simpler algorithm to compute the genomic distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607155)