Abstract
Quasimedian graphs are a tool commonly used by evolutionary biologists to visualise the evolution of molecular sequences. As with any graph, a quasimedian 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 quasimedian 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 quasimedian 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 quasimedian 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.
Original language  English 

Pages (fromto)  129138 
Number of pages  10 
Journal  Discrete Applied Mathematics 
Volume  179 
Early online date  8 Aug 2014 
DOIs  
Publication status  Published  31 Dec 2014 
Keywords
 Quasimedian graph
 Median graph
 Most parsimonious trees
 Steiner trees
 Mitochondrial evolution
Profiles

Vincent Moulton
 School of Computing Sciences  Professor in Computational Biology
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research