生産と技術

第66巻 第１号（2014）

完全線形符号の DNA 配列解析への応用
竹 中 要 一＊

研究ノート

Perfect Linear Code for DNA sequence analysis
Key Words：Bioinformatics Perfect Linear Code DNA analysis

といった現象を導きます．このタンパク質の差異は，1．はじめにその設計図である遺伝子の差異でもあります．そこ
生物であれば人も微生物もその体を形成する細胞で遺伝子が書き込まれている DNA を読む事によっ内にゲノムを持っています．ゲノムにはその生物のてタンパク質の差異を明らかにし，これに基づき生設計図がデオキシリボ核酸（DNA）という物質で物学や生物工学の研究を発展させ，疾病の解明によ書き込まれています．そのうち最も解析が進んでいる医学や治療法の発展に繋げる営みが特に 2000 年

るのは，タンパク質を規定する DNA 配列である遺以降頻繁に行われる事になりました．

伝子です．タンパク質は生物の構造を形作っていたDNA とは，五炭糖とリン酸，塩基から構成されり，酵素として生命現象を担っていたりします．分

る核酸であり，これがホスホジエステル結合によっかりやすい酵素としては，食物の消化に使われる消て一本鎖を形成します．一般には 2 つの DNA 一本化酵素が挙げられます．このタンパク質は生物種に鎖が水素結合によって螺旋状に並んだ二重螺旋構造

よって持っている種類や数が異なり，同じ役割を果が有名だと思います．DNA の塩基は，アデニン，たすタンパク質であっても生物種によって形状や効シトシン，グアニン，チミンの 4 種類が用いられて率が異なる事が知られています．また，同じ生物種おり，それぞれアルファベット一文字 A, C, G, T でであったとしてもタンパク質は同じというわけでは略記されます．遺伝子はこの 4 文字からなる単語（文なく，少しずつ異なります．例えば人間であっても字列）として扱われます．この表現法により，遺伝人それぞれ異なる事が，血液型や目の色，髪の色の子の違いは文字列の違いと言い換える事ができます．

違いに繋がったり，ある疾病に罹りやすくなったり

図 1 に ABO 式血液型を決定する遺伝子において，

図1＊

ABO 式血液型を決める遺伝子の一部．A 型，B 型，O 型で異なる塩基を着色．

Yoichi TAKENAKA
1973年6月生
大阪大学 大学院基礎工学研究科 情報数理系計算機科学分野 博士後期課程
現在、大阪大学 情報科学研究科 バイオ情報工学専攻 ゲノム情報工学講座
准教授 博士（工学） 生物情報学
TEL：06-6879-4391
FAX：06-6879-4394
E-mail：takenaka@ist.osaka-u.ac.jp

血液型によって異なる DNA 配列部分を抜粋します [1]．
遺伝子の DNA 配列の違いは，血液型だけではなく他の遺伝的特徴や遺伝性疾患に見受けられます．こ
れらの解析は，ACGT からなる文字列で表現された遺伝子群の，文字列の違いを探す事で行う事ができます．文字列比較は計算機が得意とする処理であり，生物の情報を主に解析する学問として生物情報学が誕生しました．
− 71 −

生産と技術第66巻第１号（2014）

DNA 配列の文字列を比較する研究は比較的古く，

2．完全線形符号

2 つの遺伝子の類似度を動的計画法で計算するアルゴリズムの論文が 1970 年に上梓されています [2]．

線形符号は情報を通信する際に用いられます．送それ以降も高速化を主目的とする多数のアルゴリズ

信した情報の一部が通信中に誤って受信された場合ムが提案されてきました [4-6]．この理由の一つとに，一部の誤りを検出したり，誤りを訂正したりすしては，データベースに登録される遺伝子の DNAる事ができます．図 3 を用いて説明します．今，送配列数，すなわちデータ量の増加が，計算機の速度りたい情報が 2 種類あり，それを真と偽だとします．

向上度を大きく上回っている事が挙げられます．図これを通信するために，01 のビット列との対応を2 に計算機の速度と DNA 配列を読む実験器具（DNA取ります．ここでは，真を 0000，偽を 1111 とします．

シーケンサー）の速度を比較したグラフを記します．

この 0000 と 1111 の事を符号と呼びます．この符号縦軸は，計算機が一秒間に計算できる浮動小数点演を送受信に利用します．例えば，真という情報を送算数と DNA シーケンサーが 1 回の実験で決定する

りたい場合，当方で 0000 を送信します．先方では事ができる塩基配列の数を対数で示しています．こ0000 を受信した後，送りたい情報と符号の対応表の図より，DNA シーケンサーの速度向上度が計算より，真という情報が送信されたと解釈します．符機の速度向上度を大幅に上回っている事がわかりま号を送信する場合，ノイズの影響により送信側と受す．この傾向は今後も続く事が予想されるため，よ信側とで符号が異なる事があります．例えば，0000り一層効率的で高速な計算アルゴリズムが求められを送信したのに，0100 を受信した，といった具合ています．私は情報通信を行うための方式の一つでです．この場合，0100 は送りたい情報と符号の対ある完全線形符号を，アルゴリズムの効率化と高速応表から 1111 より 0000 の方に似ている（値が同じ化に役立てる研究を行ってきました．本研究ノート

ビットの数が 0000 の方が多い）ため，0000 が送らではその基礎部分をお伝えしたいと思います．

れたと判断され，誤り訂正が行われます．この結果，真が送信されたと解釈されます．また，0110 を受信した場合，0000 と 1111 のいずれからも 2 ビット異なるため，どちらが送信されたか判断できません．
ただし，通信途上で誤りが発生した事がわかるため，これを誤り検出と呼びます．線形符号は，1) 送信に用いる符号と 2) 受信された符号から送信された符号を推定する 2 つの役割を行う方法の一種です．
生成行列と呼ばれる行列が 1 つ与えられ，行ベクトルの線形和を符号とする事から線形符号と呼ばれます．そして全ての受信語について最も似ている符号が 1 つしかない場合，完全線形符号と呼びます．

図 2 計算機の CPU の速度と DNA 配列を読む実験器具（DNA シーケンサー）の速度比較

図3

通信路と符号，誤り訂正，誤り検出の例− 72 −

生産と技術図4第66巻第１号（2014）

符号長 5 の 4 元完全線形符号の符号語．ただし DNA 配列として表現

3．ガロア拡大体 GF(4)DNA 配列は 4 つの塩基で構成されるため，私の研究では前節のような 0,1 の 2 元ではなく，4 元の完全線形符号を用います．完全線形符号では，各元が加法と乗法の 2 つの演算が定義されている必要があります．これはガロア拡大体 GF(4) の要素である事を意味します．4 つの要素を 0, 1,α,α2 とした
場合，1 +α+α2 = 0 となります．以降では，GF(4)の要素と塩基が（0, 1,α,α2）=（A, C, G, T ）と対応しているとします．
図5

符号語へと誤り訂正される DNA 配列の例

4．DNA 配列の完全線形符号道具がそろいましたので，DNA 配列を完全線形係にある DNA 配列間に辺をひいています．

符号として扱いたいと思います．ここで符号長 5 のGF(4) 上の完全線形符号を使用します．符号長 5 な

5．類似 DNA 配列探索への利用と探索空間の削ので，DNA 配列の長さは 5 となります．図 4 に示減す 64 個の DNA 配列が符号語となります．長さ 5 のDNA 配列の総数は，塩基種類 4 の 5 乗 = 1024 種類

第一節で述べましたが，データベースに登録されあります． DNA 配列を受信語として扱い誤り訂正

る DNA 配列のデータ量は膨大です．このデータベを行う事により，1024 個の DNA 配列は 64 個のースの使用法の一つに， 手元にある DNA 配列とDNA 配列へと復号されます．なお，復号前と後の類似した DNA 配列をデータベースから取り出す事

DNA 配列は高々一塩基の違いしかなく，また符号が挙げられます．完全一致の DNA 配列を見つけ出語 DNA 配列と一塩基違いの DNA 配列は必ずそのす事は容易なのですが，類似した DNA 配列を取り符号語に復号される事が保証されます．そのため，出す事になるとその難易度は跳ね上がります．例え一つの符号語に復号される DNA 配列の数が符号語ば 「 類似 」 の定義を DNA 配列中の塩基が一つ異自身を含め 16 個（=1024/64）となります．図 5 に符なるとします．長さ n の DNA 配列と完全一致する号語 CAAGT に復号される全 DNA 配列を記します．

DNA 配列は 1 種類ですが，類似した DNA 配列は図中では DNA 配列を四角で表し，一塩基違いの関1 + 3n 種類となります．同様に「類似」の定義を m− 73 −

生産と技術第66巻 第１号（2014）

箇所異なるとした場合，類似した DNA 配列は，6．おわりに1+nCm ･3 m となります．コンピュータで類似したDNA 配列を見つけ出すためには，上記の DNA 配

生物情報学の解析対象は DNA 配列以外にも多く列の種類数を全て探索する必要があるため，特に存在します．しかし基本且つ主流なのは DNA 配列

m が大きい場合には膨大な計算時間を必要とします．

だと考えています．その DNA 配列の扱い方に関す

逆にいうと，探索する必要のある DNA 配列数を減る本研究は，多くのアルゴリズムに影響を与える事らす事ができれば，計算時間の削減，すなわち探索ができます．本研究の成果が広まるよう努力していソフトウェアの高速化を実現する事ができます．私

きたいと思っています．の研究は，完全線形符号を適用する事で探索する必要のある DNA 配列数を削減可能である事を論理的参考文献に示す事にあります．

[1] Yip S. P., Sequence variation at the human ABO与えられた DNA 配列を 5 文字ごとに区切り，完locus, Ann. Hum. Genet, 66, 1-27, (2002)

全線形符号の受信語として誤り訂正を行います．こ[2] Needleman S. B., Wunsch C. D., A general

れにより DNA 配列を完全線形符号の符号列に置きmethod applicable to the search for similarities

換える事ができます．この置換により探索する必要

in the amino acid sequence of two proteins, J.のある類似した DNA 配列の種類数を大幅に削減す

Mol. Biology, 48, 443-453 (1970)

る事ができます．仮に「類似」の定義を塩基が 1 箇[3] Smith T. F., Waterman M. S., Identification of

所異なるとした場合，探索する必要のある DNA 配

Common Molecular Subsequences, J. Mol.

列数は 22. 2 + 0.00879 n となります．従来の方法とBiology, 147, 195-197 (1981)

比較した場合，定数項は大きくなっていますが，n[4] Lipman D. J., Pearson W. R., Rapid and Sensitiveの係数は 340 分の 1 程度になります．この 2 つの関Protein Similarity Searches, Science 227, 1435-係をグラフとして図 6 に示します．ここに示すように，DNA 配列を完全線形符号の受信語とみなして1441 (1985)[5] Altschul S F. et al, Basic Local Alignment Search

誤り訂正を行い，符号語に基づき探索する事によって類似する DNA 配列の探索の高速化が可能となる

Tool, J. Mol. Biology, 215, 403-410 (1990)[6] Langmead B, Trapnell C, Pop M, Salzberg S. L.,

事がわかります．これが私の研究の成果です．

Ultrafast and memory- efficient alignment ofshort DNA sequences to the human genome,
Genome Biol., 10:R25 (2009)[7] Takenaka T., Seno S., Matsuda S., PerfectHamming Code with a hash table for fastergenome mapping, BMC Genomics 12:S8 (2011)

図6

塩基が 1 カ所異なる DNA 配列を探索する場合に調べる必要のある DNA 配列数− 74 −