DNA-storageシステムの再構築アルゴリズム

DNAストレージシステムに動機付けられたこの作業は、長さN弦がDNA貯蔵チャネルを通過するDNA再構成問題を提示し、削除、挿入、置換エラーを導入します。このチャネルは、Tracesと呼ばれる送信された文字列の複数のノイズの多いコピーを生成します。DNA再構成アルゴリズムは、入力としてtトレースを受信し、元の文字列の推定を生成するマッピングです。DNA再構成問題の目標は、元の文字列とアルゴリズムの推定間の編集距離を最小限に抑えることです。この作業では、この問題についていくつかの新しいアルゴリズムを提示します。私たちのアルゴリズムは、トレースのシーケンス全体をグローバルに見て、元の文字列をデコードするために、最も短い一般的なスーパーシーケンスと最長の一般的なサブシーケンスの問題に使用される動的プログラミングアルゴリズムを使用します。私たちのアルゴリズムは、入力とトレースの数に制限を必要とせず、それ以上に、0.27のエラー確率でもうまく機能します。アルゴリズムは、シミュレートされたデータ、以前のDNA貯蔵実験のデータ、および新しい合成データセットでテストされており、再構築の精度で以前のアルゴリズムを上回ることが示されています。

Motivated by DNA storage systems, this work presents the DNA reconstruction problem, in which a length-n string, is passing through the DNA-storage channel, which introduces deletion, insertion and substitution errors. This channel generates multiple noisy copies of the transmitted string which are called traces. A DNA reconstruction algorithm is a mapping which receives t traces as an input and produces an estimation of the original string. The goal in the DNA reconstruction problem is to minimize the edit distance between the original string and the algorithm's estimation. In this work, we present several new algorithms for this problem. Our algorithms look globally on the entire sequence of the traces and use dynamic programming algorithms, which are used for the shortest common supersequence and the longest common subsequence problems, in order to decode the original string. Our algorithms do not require any limitations on the input and the number of traces, and more than that, they perform well even for error probabilities as high as 0.27. The algorithms have been tested on simulated data, on data from previous DNA storage experiments, and on a new synthesized dataset, and are shown to outperform previous algorithms in reconstruction accuracy.