如何压缩由DNA序列组成的字母表

Question

我想使用一种除了Huffman和自适应Huffman算法之外的压缩技术来压缩DNA序列，我使用c#作为编程语言。 请问有人可以帮我找到一种算法吗？ 注：我需要一种无损压缩算法。

- Sara S.

---

DNA 包含大量的碱基序列重复。任何带有字典的压缩方法都可以很好地工作。就像 Deflate 一样。 - Hans Passant

你可以参考这个C++ LZW示例，我最近尝试了一下，效果非常好。 - user7116

@HansPassant：是的，但我想使用代码的最小平均长度来提高压缩比率。 - Sara S.

Answer 1

使用DNA序列有4种可能的状态，分别是：

• 鸟嘌呤（G，00）
• 胞嘧啶（C，01）
• 腺嘌呤（A，10）
• 胸腺嘧啶（T，11）

您可以使用两位比特来存储这四种可能的状态及其括号中的值。通过这种简单方法，您将能够在一个字节中存储四个不同的值。

---

更新
如@kol所提到的，您可以使用几乎任何压缩算法进一步压缩数据。 目前，.NET附带了两种压缩方法（Deflate和GZip），更多压缩方法可以在SharpZipLib开源库中找到。

- yas4891

---

在进行编码后，生成的字节数组可以通过无损压缩算法进行压缩。请查看System.IO.Compression：http://msdn.microsoft.com/en-us/library/3z72378a.aspx - kol

@kol 很好的观点。正如 Hans Passant 指出的那样，我会把这个观点融入到答案中，因为 DNA 包含很多重复。 - yas4891