A fast and efficient algorithm for DNA sequence similarity identification

Machbah Uddin

doi:10.1007/s40747-022-00846-y

Return

A fast and efficient algorithm for DNA sequence similarity identification

2022-08-23

Machbah Uddin

Mohammad Khairul Islam *

Md. Rakib Hassan

Farah Jahan

Joong-Hwan Baek

DOI：10.1007/s40747-022-00846-y

Original

Save

View PDF

Abstract

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.

Keywords:

DNA sequence similarity

Dynamic k - k - mer count matrix

Matrix shrinking

AFproject

Benchmark dataset

Bioinformatics engineering

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.