Sequence alignment, mutual information, and dissimilarity measures for constructing phylogenies.
BACKGROUND
Existing sequence alignment algorithms use heuristic scoring schemes based on biological expertise, which cannot be used as objective distance metrics. As a result one relies on crude measures, like the p- or log-det distances, or makes explicit, and often too simplistic, a priori assumptions about sequence evolution. Information theory provides an alternative, in the form of mutual information (MI). MI is, in principle, an objective and model independent similarity measure, but it is not widely used in this context and no algorithm for extracting MI from a given alignment (without assuming an evolutionary model) is known. MI can be estimated without alignments, by concatenating and zipping sequences, but so far this has only produced estimates with uncontrolled errors, despite the fact that the normalized compression distance based on it has shown promising results.


RESULTS
We describe a simple approach to get robust estimates of MI from global pairwise alignments. Our main result uses algorithmic (Kolmogorov) information theory, but we show that similar results can also be obtained from Shannon theory. For animal mitochondrial DNA our approach uses the alignments made by popular global alignment algorithms to produce MI estimates that are strikingly close to estimates obtained from the alignment free methods mentioned above. We point out that, due to the fact that it is not additive, normalized compression distance is not an optimal metric for phylogenetics but we propose a simple modification that overcomes the issue of additivity. We test several versions of our MI based distance measures on a large number of randomly chosen quartets and demonstrate that they all perform better than traditional measures like the Kimura or log-det (resp. paralinear) distances.


CONCLUSIONS
Several versions of MI based distances outperform conventional distances in distance-based phylogeny. Even a simplified version based on single letter Shannon entropies, which can be easily incorporated in existing software packages, gave superior results throughout the entire animal kingdom. But we see the main virtue of our approach in a more general way. For example, it can also help to judge the relative merits of different alignment algorithms, by estimating the significance of specific alignments. It strongly suggests that information theory concepts can be exploited further in sequence analysis.
Complexity Science Group, Department of Physics and Astronomy, University of Calgary, Calgary, Alberta, Canada. openner@phas.ucalgary.ca
Orion
O
Penner
Peter
P
Grassberger
Maya
M
Paczuski
D000465:Algorithms; D019295:Computational Biology / Q000379:methods* / Q000592:standards; D007257:Information Theory; D008722:Methods; D010802:Phylogeny; D016415:Sequence Alignment
Bioinformatics. 2003 Mar 1;19(4):513-23
12611807
BMC Bioinformatics. 2005 Dec 12;6:298
16343337
Bioinformatics. 1999 Mar;15(3):194-202
10222406
Mol Biol Evol. 1987 Jul;4(4):406-25
3447015
Bioinformatics. 2003;19 Suppl 1:i54-62
12855437
Nucleic Acids Res. 1997 Sep 1;25(17):3389-402
9254694
Nature. 1993 Jul 29;364(6436):440-2
8332213
Nucleic Acids Res. 1994 Nov 11;22(22):4673-80
7984417
Proc Natl Acad Sci U S A. 1994 Feb 15;91(4):1455-9
8108430
J Mol Evol. 1981;17(6):368-76
7288891
Bioinformatics. 2001 Feb;17(2):149-54
11238070
Nucleic Acids Res. 2003 Jul 1;31(13):3525-6
12824358
Genome Res. 2003 Apr;13(4):721-31
12654723
Nucleic Acids Res. 2004 Jul 1;32(Web Server issue):W20-5
15215342
Mol Biol Evol. 1994 Jul;11(4):605-12
19391266
J Mol Biol. 1990 Oct 5;215(3):403-10
2231712