Optimization of Spaced K-mer Frequency Feature Extraction using Genetic Algorithms for Metagenome Fragment Classification

Arini Pekuwali (Department of Informatics Engineering, Faculty of Science and Engineering, Universitas Kristen Wira Wacana, Jalan R. Suprapto No. 35, Prailiu, Waingapu, Sumba Timur, 87113,)
Wisnu Ananta Kusuma (Department of Computer Science, Faculty of Mathematics and Natural Science, Bogor Agricultural University, Jalan Meranti, Kampus IPB Darmaga, Bogor 16680,)
Agus Buono (Department of Computer Science, Faculty of Mathematics and Natural Science, Bogor Agricultural University, Jalan Meranti, Kampus IPB Darmaga, Bogor 16680,)

Journal of ICT Research and Applications
Vol. 12 No. 2 (2018)

K-mer frequencies are commonly used in extracting features from metagenome fragments. In spite of this, researchers have found that their use is still inefficient. In this research, a genetic algorithm was employed to find optimally spaced k-mers. These were obtained by generating the possible combinations of match positions and don't care positions (written as *). This approach was adopted from the concept of spaced seeds in PatternHunter. The use of spaced k-mers could reduce the size of the k-mer frequency feature's dimension. To measure the accuracy of the proposed method we used the naïve Bayesian classifier (NBC). The result showed that the chromosome 111111110001, representing spaced k-mer model [111 1111 10001], was the best chromosome, with a higher fitness (85.42) than that of the k-mer frequency feature. Moreover, the proposed approach also reduced the feature extraction time.