Computing the blocks of a quasi-median graph

Herrmann, Sven and Moulton, Vincent ORCID: (2014) Computing the blocks of a quasi-median graph. Discrete Applied Mathematics, 179. pp. 129-138. ISSN 0166-218X

[thumbnail of final-version]
PDF (final-version) - Draft Version
Download (322kB) | Preview


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 nn aligned sequences of length mm, can compute the blocks of the associated quasi-median graph together with the information required to correctly connect these blocks together in run time O(n2m2)O(n2m2), 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.

Item Type: Article
Uncontrolled Keywords: quasi-median graph,median graph,most parsimonious trees,steiner trees,mitochondrial evolution
Faculty \ School: Faculty of Science > School of Computing Sciences
Depositing User: Pure Connector
Date Deposited: 12 Sep 2014 12:20
Last Modified: 21 Oct 2022 00:08
DOI: 10.1016/j.dam.2014.07.013

Actions (login required)

View Item View Item