A fast and efficient algorithm for DNA sequence similarity identification

doi:10.1007/s40747-022-00846-y

2022-08-23

Machbah Uddin

Mohammad Khairul Islam *

Md. Rakib Hassan

Farah Jahan

Joong-Hwan Baek

DOI：10.1007/s40747-022-00846-y

原文链接

查看原文

摘要

En 中文

DNA sequence similarity analysis is necessary for enormous purposes including genome analysis, extracting biological information, finding the evolutionary relationship of species. There are two types of sequence analysis which are alignment-based (AB) and alignment-free (AF). AB is effective for small homologous sequences but becomes N P -hard problem for long sequences. However, AF algorithms can solve the major limitations of AB. But most of the existing AF methods show high time complexity and memory consumption, less precision, and less performance on benchmark datasets. To minimize these limitations, we develop an AF algorithm using a 2D k -mer count matrix inspired by the CGR approach. Then we shrink the matrix by analyzing the neighbors and then measure similarities using the best combinations of pairwise distance (PD) and phylogenetic tree methods. We also dynamically choose the value of k for k - mer. We develop an efficient system for finding the positions of k - mer in the count matrix. We apply our system in six different datasets. We achieve the top rank for two benchmark datasets from AFproject, 100% accuracy for two datasets (16 S Ribosomal, 18 Eutherian), and achieve a milestone for time complexity and memory consumption in comparison to the existing study datasets (HEV, HIV-1). Therefore, the comparative results of the benchmark datasets and existing studies demonstrate that our method is highly effective, efficient, and accurate. Thus, our method can be used with the top level of authenticity for DNA sequence similarity measurement.

Keyword:

DNA sequence similarity

Dynamic k - k - mer count matrix

Matrix shrinking

AFproject

Benchmark dataset

Bioinformatics engineering