Computing the blocks of a quasi-median graph

DOI10.1016/J.DAM.2014.07.013MaRDI QIDQ477343zbMATH OpenOpenAlexFDO

Authors Sven Herrmann, Vincent Moulton

Publication date 3 December 2014

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

Full work available at URL https://arxiv.org/abs/1206.6135

zbMATH Keywords

Steiner treesmedian graphmitochondrial evolutionmost parsimonious treesquasi-median graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Trees (05C05) Cell biology (92C37)

Abstract: Quasi-median graphs are a tool commonly used by evolutionary biologists to visualise the evolution of molecular sequences. As with any graph, a quasi-median graph can contain cut vertices, that is, vertices whose removal disconnect the graph. These vertices induce a decomposition of the graph into blocks, that is, maximal subgraphs which do not contain any cut vertices. Here we show that the special structure of quasi-median graphs can be used to compute their blocks without having to compute the whole graph. In particular we present an algorithm that, for a collection of $n$ aligned sequences of length $m$, can compute the blocks of the associated quasi-median graph together with the information required to correctly connect these blocks together in run time $mathcalO(n^2{m}^2)$, independent of the size of the sequence alphabet. Our primary motivation for presenting this algorithm is the fact that the quasi-median graph associated to a sequence alignment must contain all most parsimonious trees for the alignment, and therefore precomputing the blocks of the graph has the potential to help speed up any method for computing such trees.

Recommendations

• Quasi-median graphs from sets of partitions
• The connected p-median problem on block graphs
• Quasi‐median graphs and algebras
• Computing median and antimedian sets in median graphs
• Axiomatic characterization of the median function of a block graph
• Quasi-median graphs, their generalizations, and tree-like equalities
• Block-vertex duality and the one-median problem
• Quasi-almostmedian graphs
• Median and quasi-median direct products of graphs
• Medians in median graphs and their cube complexes in linear time

Cites work

• scientific article; zbMATH DE number 2044913 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• An algorithm for computing cutpoints in finite metric spaces
• Axiomatic characterization of the interval function of a graph
• Blocks and cut vertices of the Buneman graph
• Graph theory
• Quasi-median graphs from sets of partitions
• Quasi-median hulls in Hamming space are Steiner hulls
• Quasi‐median graphs and algebras
• Statistical Inference of Phylogenies
• The Steiner problem in phylogeny is NP-complete
• Trees, taxonomy, and strongly compatible multi-state characters
• Visualization of quasi-median networks

Cited in

(3)

• Quasi-median graphs from sets of partitions
• Skeletons, recognition algorithm and distance matrix of quasi-median graphs
• Blocks and cut vertices of the Buneman graph

This page was built for publication: Computing the blocks of a quasi-median graph

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