Email updates

Keep up to date with the latest news and content from Algorithms for Molecular Biology and BioMed Central.

Open Access Open Badges Research

On the group theoretical background of assigning stepwise mutations onto phylogenies

Mareike Fischer14, Steffen Klaere2*, Minh Anh Thi Nguyen34 and Arndt von Haeseler4

Author Affiliations

1 Department for Mathematics und Computer Science, Ernst-Moritz-Arndt-University Greifswald, Walther-Rathenau-Strasse 47, 17487 Greifswald, Germany

2 Department of Statistics and School of Biological Sciences, University of Auckland, Private Bag 92019, Auckland, New Zealand

3 Groningen Bioinformatics Centre, University of Groningen, Nijenborgh 7, 9747 AG Groningen, The Netherlands

4 , Center for Integrative Bioinformatics ViennaMax F. Perutz Laboratories, University of Vienna, Medical University of Vienna, University of Veterinary Medicine Vienna, Dr. Bohr Gasse 9, A-1030, Vienna, Austria

For all author emails, please log on.

Algorithms for Molecular Biology 2012, 7:36  doi:10.1186/1748-7188-7-36

Published: 15 December 2012


Recently one step mutation matrices were introduced to model the impact of substitutions on arbitrary branches of a phylogenetic tree on an alignment site. This concept works nicely for the four-state nucleotide alphabet and provides an efficient procedure conjectured to compute the minimal number of substitutions needed to transform one alignment site into another. The present paper delivers a proof of the validity of this algorithm. Moreover, we provide several mathematical insights into the generalization of the OSM matrix to multi-state alphabets. The construction of the OSM matrix is only possible if the matrices representing the substitution types acting on the character states and the identity matrix form a commutative group with respect to matrix multiplication. We illustrate this approach by looking at Abelian groups over twenty states and critically discuss their biological usefulness when investigating amino acids.

Maximum likelihood; Maximum parsimony; Substitution model; Tree reconstruction; Group theory