클로버: DNA 기반 데이터 저장을 위한 트리 구조 기반 효율적인 DNA 클러스터링

탈옥시리보핵산(DNA) 기반 데이터 저장은 전통적인 저장 매체에 비해 높은 저장 용량과 긴 저장 시간을 장점으로 하는 유망한 새로운 저장 기술입니다. 그러나 DNA의 합성과 시퀀싱 과정에서 많은 종류의 오류가 무작위로 발생할 수 있어 DNA 정보를 복원하기 위한 DNA 시퀀스를 클러스터하는 것이 더 어렵습니다. 현재 사용 가능한 DNA 클러스터링 알고리즘은 생물학적 영역의 DNA 시퀀스를 대상으로 하여 DNA 저장의 시퀀스 특성에 적응할 수 없고, DNA 저장에서 수십억 개의 DNA 시퀀스에 대해서는 받아들이기 힘든 시간 소모가 발생합니다. 본 논문에서는 선형 계산 복잡도와 낮은 메모리를 갖춘 DNA 저장을 위한 효율적인 DNA 클러스터링 방법인 클로버를 제안합니다. 클로버는 간격 특정 검색을 위해 트리 구조를 사용하여 레벤슈타인 거리의 계산을 피합니다. 이론적 증명을 통해 클로버가 표준 선형 계산 복잡도와 낮은 공간 복잡성 등을 갖고 있다고 주장합니다. 실험 결과 우리의 방법은 10초 만에 1천만 개의 DNA 시퀀스를 50,000개의 클래스로 클러스터링할 수 있으며, 99% 이상의 정확도를 달성했습니다. 더욱이, 우리는 단일 가정용 컴퓨터에서 100억 개의 DNA 데이터를 전례 없는 클러스터링을 성공적으로 완료했으며, 소요 시간은 여전히 선형 관계를 만족합니다. 클로버는 https://github.com/Guanjinqu/Clover에서 무료로 제공됩니다.