Computing substitution matrices for genomic comparative analysis

LA home
Computing
Publications
 Substn matrices

Also see
Bioinformatics
 Alignment
 Compression
 TR233

Minh Duc Cao, Trevor I. Dix, and Lloyd Allison

Springer Verlag, LNCS 5476/2009, PAKDD09, isbn13: 978-3-642-01306-5, pp.647-655, 2009,
[doi:10.1007/978-3-642-01307-2_64].
 
Abstract: Substitution matrices describe the rates of mutating one character in a biological sequence to another character, and are important for many knowledge discovery tasks such as phylogenetic analysis and sequence alignment. Computing substitution matrices for very long genomic sequences of divergent or even unrelated species requires sensitive algorithms that can take into account differences in composition of the sequences. We present a novel algorithm that addresses this by computing a nucleotide substitution matrix specifically for the two genomes being aligned. The method is founded on information theory and in the expectation maximisation framework. The algorithm iteratively uses compression to align the sequences and estimates the matrix from the alignment, and then applies the matrix to find a better alignment until convergence. Our method reconstructs, with high accuracy, the substitution matrix for synthesised data generated from a known matrix with introduced noise. The model is then successfully applied to real data for various malaria parasite genomes, which have differing phylogenetic distances and composition that lessens the effectiveness of standard statistical analysis techniques.
www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Friday, 24-Nov-2017 04:30:53 EST.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.