Alignment-Free Measures for Whole-Genome Comparison

The global spread of low-cost high-throughput sequencing technologies has made a large number of complete genomes publicly available, and this number is still growing rapidly. This chapter addresses the phylogeny reconstruction problem for different organisms, namely viruses, prokaryotes, and unicellular eukaryotes, using whole-genome pairwise sequence comparison. It reviews the problem of whole-genome comparison and the most important methods and also the use of alignment-free distance function based on subword compositions. It proves that the matching statistics, a popular concept in the field of string algorithms able to capture the statistics of common words between two sequences, can be derived from a small set of independent subwords, namely the irredundant common subwords. The chapter also shows how to compute the irredundant common subwords and the matching statistics.