我们怎样才能有效地压缩DNA串

Question

DNA串可以是任何长度,包括5个字母(A,T,G,C,N)的任何组合.
什么是压缩包含5个字母(A,T,G,C,N)的字母表的DNA串的有效方法.我们可以使用较少的位来有效地压缩和检索,而不是考虑每个字母3位.任何人都可以建议一个有效压缩和检索的伪代码吗？

Answer 1

如果你愿意(a)每个字符都有不同的位大小,你可以(b)你总是从头开始阅读,而不是从中间阅读.那么,你可以得到类似的代码:

• A - 00
• T - 01
• G - 10
• C - 110
• N - 111

从左到右阅读,您只能以一种方式将比特流分成字符.您一次读取2位,如果它们是"11",您需要再读一位以了解它是什么字符.

这是基于霍夫曼编码算法

注意:
我对DNA知之甚少,但是如果chars的概率不相等(每个意思是20%).你应该将最短的代码分配给那些概率较高的代码.