Clover：ツリー構造に基づく効率的なDNAクラスタリングによるDNAベースのデータストレージ

デオキシリボ核酸（DNA）に基づくデータストレージは、従来のストレージメディアと比較して高いストレージ容量と長い保存期間の利点を持つ有望な新しいストレージ技術です。しかし、DNAの合成とシーケンシングプロセスでは多くの種類のエラーがランダムに生成されるため、DNA情報を回復するためのDNAシーケンスのクラスタリングがより困難になります。現在、利用可能なDNAクラスタリングアルゴリズムは、生物学的領域のDNAシーケンスを対象としており、これはDNAストレージのシーケンスの特性に適応できず、またDNAストレージの数十億のDNAシーケンスに対しては許容できないほど時間がかかる傾向があります。本論文では、線形計算複雑度と低メモリでのDNAストレージのための効率的なDNAクラスタリング手法「Clover」を提案します。Cloverは、間隔特定の取得のためにツリー構造を使用することでレーベンシュタイン距離の計算を回避します。我々は理論的証明を通じて、Cloverが標準的な線形計算複雑度と低空間複雑度を持つことを主張します。実験結果は、我々の手法が1000万のDNAシーケンスを5万のクラスに10秒でクラスタリングでき、99％を超える精度を満たすことを示しています。さらに、我々は単一の家庭用コンピュータで10億のDNAデータの前例のないクラスタリングを成功裏に完了し、時間の消費は依然として線形の関係を満たしています。Cloverはhttps://github.com/Guanjinqu/Cloverで無料で利用可能です。