Phylogenetic analysis of DNA sequences based on kk-word and rough set theory

• We associate a DNA sequence with a 3×2k3×2k dimensional complete word-based vector.
• It reflects information on both word frequencies and the order relation among them.
• We present a feature selection scheme on the basis of rough set theory.
• Based on the selected kk-words, a much lower dimensional feature vector is obtained.

Among alignment-free methods for sequence comparison, the model of kk-word frequencies is a well-developed one. However, most existing word-based methods neglect relationships among kk-word frequencies, while a few others focus on the correlation of kk-words but ignore the word frequency itself. In this paper, we propose a new kk-word method which succeeds in conquering the two problems.By means of characteristic sequences of a DNA sequence, we construct a 3×2k3×2k dimensional complete word-based vector. Then we present a feature selection scheme based on rough set theory (RST) to extract the most informative kk-words and use only these selected features to represent the DNA sequence. To evaluate the effectiveness of our method, we test it by phylogenetic analysis on three datasets. The first one is used as a training set, by which 869 top ranked kk-words are selected. The other two are used as the testing set. The results demonstrate that the proposed method can capture more important information and is more efficient for molecular phylogenetic analysis.