データシーケンスに関する経験的無損失圧縮

科学分野:

• 情報理論
• データ圧縮
• 統計的推論

背景:

• コルモゴロフの複雑性は,無損失のデータ圧縮のための計算不可能な理論的境界を提供します.
• シャノンのソースコーディング定理は,平均圧縮をnHとして定義し,nはシーケンス長,Hはエントロピーである.
• 最大確率推定 (MLE) は,しばしば真の圧縮枠を過小評価する.

研究 の 目的:

• 個々のデータシーケンスの無損失圧縮を導出し分析する.
• データの圧縮のための標準化された最大確率分布 (NML) の最適性を調査する.
• 圧縮された計算を離散データと連続データの両方に拡張し,バイオインフォマティクスに応用する.

主な方法:

• ミニマックス意味での最適であることが示されているNML分布を使用します.
• NMLのアシンプトティックコードの長さを得るために,局所アシンプトティック正規性を適用する.
• 最適なコードの長さを予測するベイジアンアプローチを開発し,混合コードに導きます.
• 異なる解析モデルを使用して,タンパク質をコードするDNA配列の圧縮限界を計算する.

主要な成果:

• NMLのコードの長さは,分析的にnH (θ^n) + (d/2) log (n/2π) + log (∫) となる.
• ベイジアン予測で得られた混合コードの長さは,nH (θ^n) + (d/2) log (n/2π) + log (n) です.
• DNA配列の圧縮は,解析がアミノ酸コドンと整合すると最大化され,実用的な応用が示されます.
• 経験的な圧縮境界は,辞書サイズが大きくなると改善されます.

結論:

• NML分布は,データ圧縮限界に最適な計算可能なアプローチを提供します.
• 派生したアシンプトティック式は,離散的および連続的なデータ圧縮の両方に正確な推定を提供します.
• 解析戦略は,特に生物学的配列の圧縮効率に大きな影響を与える.
• この研究は,さまざまなデータ型における理論的な圧縮限界を理解し,計算するための堅固な枠組みを提供します.