Computing the blocks of a quasi-median graph

DOI10.1016/J.DAM.2014.07.013zbMATH Open1303.05029arXiv1206.6135OpenAlexW2151358997MaRDI QIDQ477343FDOQ477343

Authors: Sven Herrmann, Vincent Moulton 

Publication date: 3 December 2014

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

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.

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

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

zbMATH Keywords

Steiner treesmedian graphmitochondrial evolutionmost parsimonious treesquasi-median graph

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Statistical Inference of Phylogenies
• The Steiner problem in phylogeny is NP-complete
• An algorithm for computing cutpoints in finite metric spaces
• Title not available (Why is that?)
• Quasi‐median graphs and algebras
• Axiomatic characterization of the interval function of a graph
• Quasi-median hulls in Hamming space are Steiner hulls
• Trees, taxonomy, and strongly compatible multi-state characters
• Quasi-median graphs from sets of partitions
• Blocks and cut vertices of the Buneman graph
• Title not available (Why is that?)
• 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)