Alignment free comparison: k word voting model and its applications

Abstract

Alignment free sequence comparison is widely used in sequence analysis, especially in computational biology for large scale similarity comparison. In this paper, we propose a word voting model to compare the biological sequences without alignment. Unlike many comparison methods based on the k word, this model does not use the k word frequency or statistics. Thus there is no limitation on the choice of k. Instead, we used information entropy of gamma distribution to characterize the differences among biological sequences in this model. Finally, we employed the model to do the similarity search and phylogenetic tree construction to further validate the model.

Keywords: Gamma distribution; Information entropy; Large scale comparison.