パスワードを忘れた? アカウント作成
13177196 journal
日記

phasonの日記: 噴水符号を用いたDNAストレージの大容量化・高信頼化 4

日記 by phason

"DNA Fountain enables a robust and efficient storage architecture"
Y. Erlich and D. Zielinski, Science, 355, 950-954 (2017).

DNAは非常にコンパクトな領域に膨大な情報を保持している.例えば我々人間は一人あたりおよそ40兆個の細胞で出来ているが,その一つ一つの細胞内にはおよそ60億塩基対(2倍体の場合)からなる染色体があり,これを単純に1 塩基対=2 bit(塩基が4種類あるため)とすればおよそ1.5 GByteに相当する.
細胞一つの中のさらに核一つでこれだけの情報を記録でき,さらに二重らせん構造によるデータ保護も持ち合わせているため,「DNAをストレージに使えるのではないか?」という研究が行われるのは自然な流れであると言え,実際に多くの研究が行われている.これらの研究の多くでは,データを細かなセグメントに分割し(*),それぞれのセグメントを塩基配列として表現,これを合成後にPCR増幅することで十分な安定性を備えたデータストレージとして扱っている.

(*)これは,あまりに長い塩基配列を合成したり迅速に読んだりすることが困難(または不可能)である事に由来する.数百程度なら非常に安く&高速に合成が出来るが,数万~数十万塩基対の合成は現時点ではさすがに困難である.

しかしながら,DNAにデータを記録する場合にはさまざまな形でのデータの欠落に備える必要がある.例えば一塩基変異であるとか,PCRによるDNAの増幅の際に一部の配列が増えずに失われてしまう,などである.前者のような1 bitの変異に関してはデータセグメントごとに誤り訂正符号なものを付け加えておくことで対処できるが,あるセグメントが丸ごと失われてしまうような後者の問題の場合,データを複数の分割方式でエンコードしておくなどデータの重複が多くなり,結果としてデータ格納効率が落ちてしまうと言う問題があった.
DNAは4種類の塩基を持つため,理想的には2 bit/塩基対のデータ密度が実現できる.まあ実際には不安定な配列(同じ塩基が続くとか,GCのペアが多すぎる/少なすぎる,など)が存在したりするため使用できる塩基配列が制限されたり,DNAの複製過程での取りこぼしや変異などの可能性を加味し,シャノン限界として1.83 bit/塩基という値が提唱されている.ところがこれまでに報告されているDNAストレージでは,多くの例で0.8~0.9 bit/塩基,高いものでも1.14 bit/塩基の情報密度にとどまっている.これはデータの欠落を防ぐためにかなりの冗長性を入れていることがその一つの理由である.

耐障害性を高めながらも無駄な冗長性を出来るだけ減らし,理論値に近いデータ密度を実現することは出来ないのだろうか?幸いなことに,現代の情報処理技術の進展は,この問題の良い解決策を提供してくれている.それが「噴水符号(Fountain Code)」である.
この符号化は元々,インターネットなどを介したマルチキャストなどのために開発されているものだ.ネット配信などでは,膨大な数の受信者に対し同一のデータを配信する.ところが単純にデータを分割して配信するだけだと,各経路ごとに一部のパケットが抜け落ちることでの再送要求がサーバに集中する可能性がある.各経路でどのパケットが落ちるかはランダムであるため,これはありとあらゆるパケットの再送要求が集中することを意味しており,非常に具合が悪い.これを解決するために開発された噴水符号では,元々のパケットをランダムに(実際にはランダムというか,疑似乱数的というか,ともかくこのパケットペアの選びかたにもいろいろ工夫があるらしい)二つ選択し,それらの論理和をとったもの(であるとか,とにかく何らかの演算を行ったもの)を配信する.サーバ側ではこの作業を延々と繰り返し,さまざまなパケットペアの相関に相当するデータ(これをdroplet:水滴と呼ぶ)が次々に作成され配信され続ける.受信側でいくつかのパケットがロスしていたとしても,別なパケットいくつかから必要なデータを復元することが出来る.あまり正確ではないが,A-B相関のパケットが失われても,A-C相関,B-C相関の二つのパケットから再計算できるような感じだ.
この噴水符号は,元々のデータよりほんの少しだけ多いデータを使用することで,かなりの確率で元データが復元できる事を特徴としている.つまり,データの無駄を非常に小さくしながらも高い復元性・耐障害性を備えた符号化である事が知られているわけだ.この符号化を利用すれば,多少のデータの欠落が起こるような状況であっても,高効率でデータを保持できる.まさに,DNAストレージにうってつけ,と言うわけだ.
そんなわけで今回著者らは,DNAの塩基配列としてデータを保持するための符号化に噴水符号を利用,それにより非常に高効率にデータを保存できたよ,という事を報告している.

では,実際の実験を見ていこう.
データのエンコードの仕方としては,まずはデータを32 byteのセグメントに分割する.今回の場合では総計2,146,816 byte = 67,088セグメント相当のデータをDNAにエンコードする.このデータに入っているのはOS(こういった際によく利用されるコンパクトなKolibriOS),テキストファイル(Amazonギフトカードの番号),パイオニア探査機の金属板の画像ファイル,Shannonの論文のPDF,ムービーファイル,あとなぜかZipbombである.実際のエンコードに当たっては,疑似乱数列を用いて次々と2つのセグメントを選択してそれらの論理和を作成,2 bitを単純に4種類の塩基に置き換える.この段階で最低限のチェックルーチンが入り,生物学的に無効度の高い配列(同一塩基の連続やGC含量の過多)は廃棄される.問題が無ければ,32 byteの論理和(=128塩基対)の頭と尻尾に読み取り等のためのアダプターとなる塩基配列(両方とも24塩基対),疑似乱数列のどの部分の計算結果なのかを表すタグ(4 byte=16塩基対),データ化け対策の誤り訂正符号(リード・ソロモン.2 byte=8塩基対)を付け,全長200塩基対の「パケット」が完成する.でもってこの「パケット」を,噴水符号に基づき次々と組み合わせるデータのセグメントを変えながら作成していくわけだ.
元データを単純に冗長性無しで変換すると67,088種類のパケットとなるわけだが,疑似乱数で組み合わせを作っているため完全に網羅するにはもうちょっと種類を増やしておきたい&DNA増幅の途中で特定の配列が欠落する事を想定しての冗長性確保のため,著者らは元データに+7%となる72,000種類のパケットが出来るまでパケットの作成を続けた.大まかに,元データの5~10%増しが推奨だそうだ.これで読み出せれば,1 塩基あたりおよそ1.57 bitのデータという事になり(この計算では,パケット頭と尻尾のアダプター配列は計算に入れていないようだ),既存の最高値である1.14 bit/塩基を超えシャノン限界の1.83 bit/塩基に大きく近づくこととなる.

では,実際にこいつがきちんとデータを保持できていたかを見ていこう.
まずはPCRで十分に増やしたDNAプールの中身を片っ端から読んで,元データが復元できるかどうかのチェックである.最近の読み取り機だと一日に数十億塩基対が読めるそうなので,まあそこそこの数を読むことが可能だ.著者らは3200万パケットを読み出して(当然膨大な量の重複がある),そこから元データを1 bitのロスもなく再現できることを確認した.と言っても3200万パケットは,パケットの種類が7.2万しかないことを考えると読み過ぎではある.そこで読み出した3200万の中から,ランダムに75万パケットを選んでそこから元データを復元し,これも問題無いことを確認した.この段階では1.3%のパケットロスが生じたようだが,データの復元には問題にならなかった.
さらに著者らは,作成したデータがPCRによる増幅とそこからの取り分けに耐えて生き延びられるかどうかを検証した.前述の通り,DNA複製過程においてはデータの変質や取りこぼしが起こる可能性が有り,冗長性無しではデータ化けや一部ロスが発生すし,増やした溶液の一部だけをとる部分でも濃度の不均一化などが起こる可能性があり,データ損失の可能性が生まれる.まず著者らはPCRを10回行って元のDNA量を210に増やす.増やしたDNA3 μgから10 ngをとり,「それをPCRにかけ2倍のDNA量に増やした後に25 μlから1 μlだけ抜き出して次に回す」という操作を9回繰り返した.これだけの増幅を全量に対して行ったとすると,データのコピー数は最大で1015倍以上に増えており,実用上無限の複製が可能と言うことに対応する.これだけの複製を行うとさすがにデータの質は劣化していたが(7.8%がパケットロス),それでも500万パケットも読み取ってやれば1 bitのエラーもなく元データを復元,そのデータからOS立ち上げたりファイル読んだりが可能であった.
最後に,どの程度のデータ密度が可能であるか?を検証している.一応過去の論文で,DNAストレージの理論的なデータ密度の限界は1グラムあたりおよそ680ペタバイトであると概算されているのだが,今回著者らは元データを希釈 → その一部をとって読み出し → 希釈……として読み出し限界を探ることで,どの程度のデータ密度が実現できたかを調べている.その結果,元のデータプールから10 ngをとってきて,その1/10をとって10倍希釈して読み出し,と言うのを続けた結果,10 pgまでは問題無く元データ2,146,816 byteが復元できた.もう一回希釈するとダメだったので,ここから2.15 Mbyte/10 pg~215ペタバイト/g,という事になるだろう.

そんなわけで,「情報分野で使われている効率の良いパケットロス対策法を導入したら,DNAストレージの性能がだいぶ上がったよ」という論文であった.
読み取り速度は昔に比べると劇的に上がっているとは言え,いつかこういったデータ保存法が何かに使われる日が本当に来るのだろうか?(あるにしても,日常的な用途と言うよりは,大規模なデータをものすごい数複製作って長期冷凍保存しておく,とかそういう用途になるのか?)

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

UNIXはシンプルである。必要なのはそのシンプルさを理解する素質だけである -- Dennis Ritchie

読み込み中...