An information-based sequence distance and its application to whole mitochondrial genome phylogeny.
BACKGROUND
Traditional sequence distances require an alignment and therefore are not directly applicable to the problem of whole genome phylogeny where events such as rearrangements make full length alignments impossible. We present a sequence distance that works on unaligned sequences using the information theoretical concept of Kolmogorov complexity and a program to estimate this distance.


RESULTS
We establish the mathematical foundations of our distance and illustrate its use by constructing a phylogeny of the Eutherian orders using complete unaligned mitochondrial genomes. This phylogeny is consistent with the commonly accepted one for the Eutherians. A second, larger mammalian dataset is also analyzed, yielding a phylogeny generally consistent with the commonly accepted one for the mammals.


BACKGROUND
The program to estimate our sequence distance, is available at http://www.cs.cityu.edu.hk/~cssamk/gencomp/GenCompress1.htm. The distance matrices used to generate our phylogenies are available at http://www.math.uwaterloo.ca/~mli/distance.html.
Li
M
M
Bioinformatics Laboratory, Computer Science Department, University of Waterloo, N2L 3G1, Canada. mli@wh.math.uwaterloo.ca
Badger
J H
JH
Chen
X
X
Kwong
S
S
Kearney
P
P
Zhang
H
H
D000818:Animals; D004272:DNA, Mitochondrial / Q000032:analysis* / Q000145:classification; D006801:Humans; D008432:Mathematical Computing; D010802:Phylogeny; D012377:Rodentia / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods; D017422:Sequence Analysis, DNA; D012984:Software
D004272:DNA, Mitochondrial