Computing the blocks of a quasi-median graph

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

Preview

PDF (final-version) - Draft Version Download (322kB) | Preview

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 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
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	Pure Connector
Date Deposited:	12 Sep 2014 12:20
Last Modified:	13 Jun 2023 08:23
URI:	https://ueaeprints.uea.ac.uk/id/eprint/50087
DOI:	10.1016/j.dam.2014.07.013

Downloads

Actions (login required)

View Item