技術要約：HiDAC – ゲノム配列のための階層的辞書補助圧縮フレームワーク

1. 問題提起

次世代シーケンシング（NGS）によって生成されるゲノムデータの急速な拡大は、ストレージ、転送、および解析において重大な課題を生み出している。既存のロスレス圧縮ツール（Gzip、Bzip2など）は存在するものの、これらは一般的なテキスト用に最適化されており、DNA配列特有の性質（4文字の小さなアルファベットや、反復パターンの蔓延など）を活用できていない。

既存のDNA特化型圧縮手法は、概ね以下の3つのカテゴリに分類されるが、それぞれに限界がある：

• 統計的手法： 確率モデル（マルコフ連鎖など）に依存するが、長距離依存性や入れ子状の反復（nested repeats）への対応に苦慮することが多く、高い計算リソースを必要とする。
• リファレンスベースの手法： 既知のリファレンスゲノムとの差異をエンコードする。これらは関連性の高いゲノムには効果的だが、メタゲノムサンプルや、適切なリファレンスが存在しない分岐した生物種には適用できない。
• 辞書ベースの手法： 再帰的な部分文字列をトークンに置き換える。しかし、既存のアプローチの多くは貪欲な戦略を用いており、入れ子状または階層的な反復を見逃しやすく、新しいデータセットごとに辞書を再構築する必要がある。決定的なことに、これらの手法による圧縮出力は不透明（opaque）であり、分析タスク（部分文字列検索、頻度解析など）を実行するには完全な展開（デコンプレッション）が必要となり、ダウンストリーム解析における圧縮のメリットを打ち消してしまう。

本論文は、高い圧縮効率を提供しつつ、**圧縮領域解析（compressed-domain analysis）**を可能にする手法、すなわち、完全な展開を行うことなく、半圧縮された（トークン化された）表現に対して直接操作を行うことができる手法の欠如を指摘している。

2. 手法

HiDAC（Hierarchical Dictionary-Aided Compression：階層的辞書補助圧縮）は、最適な反復パターンを特定し、それらを効率的にエンコードするために設計された2段階のフレームワークである。

2.1 前処理

入力されたDNA配列は、ヘッダー、空白、および無効な文字を除去することでクリーニングされる。有効なヌクレオチド（A, T, G, C）は大文字に変換される。非標準的な文字は、ロスレスな再構成を確実にするために、メタデータ（位置、文字、ランレングス）として記録される。

2.2 階層的辞書の作成

核心となる革新は、入れ子状の辞書を構築するための反復的かつコスト誘導型の置換戦略である：

1. 初期化： アルゴリズムは、最も頻度の高い2-mer（塩基のペア）を特定する。同数の場合は、シャノン・エントロピーを用いて、より情報量が高いパターンを選択する。
2. 反復置換： 選択されたパターンは、一意の非塩基トークンに置き換えられる。このトークンは辞書に格納され、その後の反復において、より長い複合パターンの形成に参加することができる。
3. コスト関数： カスタムのコスト関数が、置換が有益であるかどうかを判断する。これは、配列長の純減およびトークン頻度のバランスを評価する。
   • 塩基のみで構成されるパターンの場合、単純な頻度チェックが使用される。
   • 複合パターン（既存のトークンを含むもの）の場合、アルゴリズムは OriginalCost（現在のトークンによって表される総ヌクレオチド内容）と NewCost（置換後の内容）を計算する。置換は、NewCost > θ1 * OriginalCost である場合にのみ受け入れられ、これにより、わずかな利得による語彙の肥大化を防ぐ。
   • 追加の効率チェックにより、置換後にトークンごとにエンコードされる平均ヌクレオチド数が改善されることを確認する。
4. 終了： 最大反復回数に達するか、これ以上有益な候補が存在しないまで、このプロセスを繰り返す。

2.3 マルチパターンマッチングと置換

辞書が構築された後、効率的なパターンマッチングのために Aho-Corasickアルゴリズム が採用される：

• オートマトン構築： すべての辞書パターンからトライ（trie）を構築し、線形時間でオーバーラップする一致を処理するために、失敗リンク（failure links）と出力リンク（output links）を付加する。
• 貪欲な置換： 入力配列をスキャンする。各位置において、複数のパターンが一致する場合、アルゴリズムは最長のものを選択し、長さが等しい場合は最も頻度の高いパターンを選択する。この「貪欲な」アプローチにより、ステップごとの圧縮を最大化する。
• 配列は、トークンのストリームと一致しないリテラル塩基へと変換される。

2.4 エントロピー符号化

トークン化された配列は、**コンテキストモデル化された算術符号化（context-modelled arithmetic coding）**を用いてさらに圧縮される：

• コンテキストモデリング： オーダー1のコンテキストモデルが、直前のトークンに基づき、あるトークンの出現確率を推定する。
• スムージング： 未知の遷移を扱うためにラプラス・スムージングが適用され、ゼロ確率の発生を防ぐ。
• 符号化： 配列はビットストリームへとエンコードされる。最終的な出力ファイルには、圧縮されたビットストリーム、階層的辞書（整数文法として）、およびロスレス再構成のためのメタデータが含まれる。

2.5 圧縮領域解析

HiDACは、完全な展開を行うことなく、トークンストリームに対して直接解析を行うことをサポートする：

• トークンフィルタリング： クエリパターンの最初の文字が、あるトークンの展開内に存在しない場合、そのトークンは完全にスキップされる。
• 遅延展開： クエリを包含する可能性があるトークンのみが展開される。
• オートマトンマッチング： クエリを、残りのトークンの展開された塩基に対して一致させるために、Knuth-Morris-Pratt (KMP) オートマトンが使用される。これにより、頻度カウントやパターン検索を、大幅に縮小されたデータセットに対して実行することが可能になる。

3. 主な貢献

• 階層的辞書構築： 配列を逐次的に処理する標準的な辞書手法とは異なり、HiDACはトークンが他のトークンを表すことができる入れ子状の階層を構築し、複雑な構造的規則性を捉える。
• コスト誘導型選択： コスト関数（NewCost 対 OriginalCost）の導入により、辞書の拡張が圧縮利得を最大化し、トークン頻度のバランスを維持するように厳密に制御される。
• 圧縮領域での利用可能性： 本フレームワークは、半圧縮されたデータに対して分析操作（パターン検索、頻度カウント）を可能にし、完全な展開の必要性を排除する。トークン化された表現は単なる保存形式ではなく、高速なダウンストリームタスクのための機能的な構造である。
• 再利用性： 辞書はリファレンスから一度構築されれば、同じゲノムクラス内の他の配列に適用でき、大規模なデータセットに対する前処理のオーバーヘッドを削減できる。

4. 実験結果

本手法は、Escherichia coli、Mycobacterium tuberculosis、ヒトゲノム、および15種のベンチマークセットを含む、5つの多様なデータセットで評価された。

• 圧縮性能：
  • HiDACは、細菌データセット（DS 1 および DS 2）で約 76%、ヒト染色体（DS 3）で 76.38% のファイルサイズ削減（節約されたスペース）を達成した。
  • 一般的な圧縮ソフト（gzip, bzip2, zstd, lzma, brotli）および専門的なゲノム圧縮器であるNAFを、一貫して上回った。
  • 最先端のMDLベースの圧縮器であるHMGとの比較において、HiDACは多様なゲノムタイプにわたってより一貫したパフォーマンスを示し、圧縮率の四分位範囲も狭かった。
• 辞書の汎用性：
  • ヒト染色体の90%から構築された統一辞書は、ヒトゲノム全体を圧縮することに成功し、局所的および全域的な反復モチーフの両方を捉えた。
  • 学習されたトークンの分析により、本手法が異なる種にわたって、ジヌクレオチド（例：TT, AA）やトリヌクレオチド（例：TAA, ATG）といった生物学的に重要なパターンを確実に特定していることが明らかになった。
• 圧縮領域解析の速度：
  • トークン化された表現上で直接行われた部分文字列頻度分析は、元の配列に対して 2.6–2.8倍高速 であった。
  • このスピードアップは、クエリ長（13–466塩基）および、多様なサイズや反復構造（例：Drosophila miranda やヒト染色体4）を持つゲノムにおいて一貫していた。

5. 意義と主張

著者らは、HiDACがゲノムデータの「ストレージ効率」と「分析のアクセシビリティ」という二重の課題に対処していると主張している。

• 効率性： 本手法は、既存の最先端ツールと比較して、同等または優れた圧縮率を提供し、ストレージおよび転送コストを効果的に削減する。
• 分析能力： 半圧縮されたデータに対して操作を可能にすることで、ゲノム解析に伴う計算オーバーヘッドを軽減する。論文は、トークン化された表現が単なる保存形式ではなく、より高速なダウンストリームタスクのための機能的な構造であることを示している。
• 堅牢性： 本フレームワークは強力な汎用性を示しており、特定の参照ゲノムを必要とすることなく（代表的な辞書が確立された後は）、多様な種やゲノムサイズに対して良好に機能する。

結論として、コスト関数やコンテキストモデリングのさらなる洗練の余地はあるものの、現在のフレームワークは、圧縮されたゲノムデータに対して直接計算を行う能力と、圧縮性能を効果的に両立させている。