Go言語によるバイナリ操作と遺伝子圧縮
David Kopecによる「クラシックコンピュータサイエンスプロブレムズ イン パイソン」を読んでCSアルゴリズムの復習をしていました。
最初の問題の一つは遺伝子圧縮で、核酸の文字列（"ACGTA..."）をバイナリに変換してメモリ上のサイズを削減することを目標としています。
圧縮データはダウンロードやアップロードする内容が少なくても、同じ情報を得られるため素晴らしいです。
'ACGT'の4文字に限定される核酸の性質は、単純な整数値である - 0, 1, 2, 3 - を使用してエンコードするのに適しています。
数値を保存する方が、UTF-8やASCIIで独特の文字を表現するバイトの集まりである文字列を保存するよりもメモリ効率が良いです。
その本はPythonで圧縮/解凍アルゴリズムを実装していますが、Goで書いてみて二進数についての概要を提供するのも良い学習エクササイズだと思いました。
バイナリの基礎
普段はほとんどの状況で数値を表すのに基数10を使います。しかし、スイッチのオン/オフの状態など、ハードウェアを使用してデータをモデル化したい場合は基数10は扱いにくいです。
しかし、基数2はスイッチを使って簡単にモデル化でき、コンピュータには自然に適しています。
| 10進数 | 2進数展開 | バイナリ |
|---|---|---|
| 0 | 0 (20) | 0 |
| 1 | 1 (20) | 1 |
| 2 | 1 (21) + 0 (20) | 10 |
| 3 | 1 (21) + 1 (20) | 11 |
| ... | ... | ... |
| 7 | 1 (22) + 1 (21) + 1 (20) | 111 |
| 8 | 1 (23) + 0 (22) + 0 (21) + 0 (20) | 1000 |
指数の係数が10進数のバイナリ表現を与えます。
Go言語におけるバイナリ操作
Goでバイナリを楽しんでみましょう。
バイナリリテラルは、0b101のような0bプレフィックスで書かれます。
package main
import "fmt"
func main() {
fmt.Println(0b11) // 3
fmt.Println(0b11 == 3) // true
fmt.Println(0b1000 == 8) // true
// 左シフトはビットを左に移動し、右側に0を導入し、数を増やします。
fmt.Println(0b10 << 1) // 4、すなわち100
fmt.Println(0b1 << 2) // 同じく4
fmt.Println(0b1<<2 == 0b10<<1) // true
// 右シフトはビットを右に移動し、列を失い、数を減らします。
fmt.Println(0b011>>1 == 1) // true
fmt.Println(0b1111 >> 2) // 3、すなわち11
fmt.Println(0b1110>>2 == 3) // true
// AND演算子&を使って両方の列が1の場合は1を、それ以外は0を返します。
fmt.Println(0b110&0b100 == 0b100) // true
fmt.Println(0b01&0b00 == 0) // true
// OR演算子|を使ってどちらかの列、または両方の列が1の場合は1を、それ以外は0を返します。
fmt.Println(0b11|0b01 == 0b11) // true
fmt.Println(0b100|0b011 == 0b111) // true
// XOR演算子^を使って列が異なる場合のみ1を、それ以外は0を返します。
fmt.Println(0b11^0b00 == 0b11) // true
fmt.Println(0b100^0b101 == 0b1) // true
}
遺伝子圧縮アルゴリズム
遺伝子圧縮問題に適用されたときに、バイナリ操作は本領を発揮します。
さあ始めましょう。
mkdir geneCompression
cd geneCompression
main.goファイルを作成し、CompressedGene型を定義します。
package main
type CompressedGene struct {
bits int
}
コンストラクタ関数を作り、内部で呼び出されるcompressというプライベートメソッドを作ります。これは遺伝子をビットフィールドに保存します。
func (cg *CompressedGene) compress(gene string) error {
cg.bits = 1 // 先行値として使えるように、最初の核酸として00や01を保存することができる
for _, nucleotide := range strings.ToUpper(gene) {
cg.bits <<= 2 // 左シフトで00のスペースを作る
switch nucleotide {
case 'A':
cg.bits |= 0b00
case 'C':
cg.bits |= 0b01
case 'G':
cg.bits |= 0b10
case 'T':
cg.bits |= 0b11
default:
return fmt.Errorf("無効な核酸：%c", nucleotide)
}
}
return nil
}
// NewCompressedGeneは圧縮された遺伝子の構造体を参照として提供します。
func NewCompressedGene(gene string) (*CompressedGene, error) {
cg := CompressedGene{}
err := cg.compress(gene)
if err != nil {
return nil, err
}
return &cg, nil
}
圧縮の際、00や01を最初の要素に加えたときに、先頭のゼロが無視されるため0ではなく1をセンチネル値としてスタートします。
左シフトを使って遺伝子を保存する２つの列を作ります。or equals |= オペレータを使用して、遺伝子に応じて最も右側のビットの値を変更して保存します。
解凍は圧縮方法の逆です。
// Decompressはビットを文字列に展開します。
func (cg *CompressedGene) Decompress() (string, error) {
gene := ""
// -1 は先行値を無視するためです
for i := 0; i < bitLength(cg.bits)-1; i += 2 {
rightShifted := cg.bits >> i
fmt.Printf("%d 右にシフトした：%b\n", i, rightShifted)
// 最も右側の2ビットを取得します
rightPair := rightShifted & 0b11
switch rightPair {
case 0b00:
gene += "A"
case 0b01:
gene += "C"
case 0b10:
gene += "G"
case 0b11:
gene += "T"
default:
return "", fmt.Errorf("無効なビット列：%d", rightPair)
}
}
return reverse(gene), nil
}
func bitLength(n int) int {
return int(math.Floor(math.Log2(float64(n))) + 1)
}
func reverse(s string) string {
r := []rune(s)
for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r)
}
整数値にあるビットの数を決定するためにbitLengthヘルパー関数を使用し、展開した文字列を逆にするためにreverse関数を使用します。ビットから遺伝子に向かって左から右に進むため、構築する文字列は元のものと逆です。そのため最終的なステップとして文字列を逆にする必要があります。
全てが期待通りに動作するのかテストしましょう！
func main() {
gene := "ACGT"
fmt.Printf("元の遺伝子：%s\n", gene)
compressed, err := NewCompressedGene(gene)
if err != nil {
log.Fatalln(err)
}
fmt.Printf("ビット：%b\n",compressed.bits)
decompressed, err := compressed.Decompress()
if err != nil {
log.Fatalln(err)
}
fmt.Printf("元の遺伝子と一致する：%v\n", decompressed == gene)
}
go run main.go
元の遺伝子：ACGT
ビット：100011011
0 右にシフトした - 100011011
2 右にシフトした - 1000110
4 右にシフトした - 10001
6 右にシフトした - 100
元の遺伝子と一致する：true
このアルゴリズムが苦戦するのは大きな文字列シーケンスになった場合です。
gene の値を変えて再実行しますと、予期せぬ結果になる可能性があります。
func main() {
gene := strings.Repeat("TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATA", 100)
compressed, err := NewCompressedGene(gene)
if err != nil {
log.Fatalln(err)
}
fmt.Printf("ビット：%b\n", compressed.bits)
decompressed, err := compressed.Decompress()
if err != nil {
log.Fatalln(err)
}
fmt.Printf("元の遺伝子と一致する：%v\n", decompressed == gene)
}
大きな遺伝子文字列はbits intフィールドが簡単に64ビットの限界までオーバーフローしてしまいます！Goのint型は基盤システムによって32ビットまたは64ビットです。しかし、この限界は望ましくありませんので、私達はパワフルなbig.Intを活用しなければなりません。
big.Intを使う
big.Int型は&や<<のようなバイナリ操作記号をサポートしていませんが、同じことをするメソッドがあります。
Or、And、Lsh（左シフト）、Rsh（右シフト）メソッドをロジックで使うことができます。
// CompressedGeneは圧縮された形式の遺伝子シーケンスをモデル化します
type CompressedGene struct {
bits *big.Int
}
func (c *CompressedGene) compress(gene string) error {
c.bits = big.NewInt(1) // 先行値
for _, nucleotide := range strings.ToUpper(gene) {
c.bits.Lsh(c.bits, 2)
switch nucleotide {
case 'A':
c.bits.Or(c.bits, big.NewInt(0b00))
case 'C':
c.bits.Or(c.bits, big.NewInt(0b01))
case 'G':
c.bits.Or(c.bits, big.NewInt(0b10))
case 'T':
c.bits.Or(c.bits, big.NewInt(0b11))
default:
return fmt.Errorf("無効な核酸：%c", nucleotide)
}
}
return nil
}
// Decompressは圧縮されたビットシーケンスを
// A,C,G,Tの核酸文字列に展開します。
func (c *CompressedGene) Decompress() (string, error) {
gene := ""
// -1 は先行値を無視するためです
for i := 0; i < c.bits.BitLen()-1; i += 2 {
rightShifted := &big.Int{} // 元の値を変更しないためのローカル値
rightShifted.Rsh(c.bits, uint(i))
// 最も右側の2ビットを取得。
rightBits := (rightShifted.And(rightShifted, big.NewInt(0b11))).Uint64()
switch rightBits {
case 0b00:
gene += "A"
case 0b01:
gene += "C"
case 0b10:
gene += "G"
case 0b11:
gene += "T"
default:
return "", fmt.Errorf("無効なビット列：%d", rightBits)
}
}
return reverse(gene), nil
}
コンストラクタは同じままです。
圧縮アルゴリズムの価値を判断できるように、メイン関数を調整してバイトサイズを出力しましょう。
func main() {
s := strings.Repeat("TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATA", 100)
c, err := NewCompressedGene(s)
if err != nil {
log.Fatalln(err)
}
fmt.Printf("文字列バイト数：%d\n", len([]byte(s)))
fmt.Printf("圧縮されたバイト数：%d\n", len(c.bits.Bytes()))
d, err := c.Decompress()
if err != nil {
log.Fatalln(err)
}
fmt.Printf("元の遺伝子と一致する：%v\n", d == s)
}
go run main.go
文字列バイト数：8600
圧縮されたバイト数：2151
true
やりましたね！遺伝子をbig intにエンコードすることで、かなりのメモリを節約できました。
これにより、Goのbig.Int型についてや、データを圧縮するためにバイナリ操作を適用する方法を学びました。
この問題を解決するための興味深いコンピューティングの問題とその巧妙な解決法をプログラムするのは楽しいデモンストレーションでした。
この本にある残りのアルゴリズムを発見して実装するのが楽しみです！
こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/karanveersp/binary-ops-and-gene-compression-in-go-4am5
