文字列の類似度を測る(4) 置換の起こりやすさとDNA

概要
文字列の類似度を測る際に置換という操作を考えるが、この操作の起こりやすさによって類似度を調整する仕組みがある。この仕組みは言語やDNAの分析にも役立つ。

はじめに

前に文字列の類似度を測る手法として編集距離について紹介した。これは、文字の置換などの編集がどれだけ必要かということに基づいて、文字列の類似度を測る手法である。

しかし、置換と言っても、起こりやすい置換とそうでない置換がある。前に紹介した手法では、置換の起こりやすさについて想定してこなかったが、もし想定したとしたらどうなるかということが今回扱いたい内容である。なお、置換の起こりやすさについての話は、DNAの塩基配列の変化のモデルを例とすると分かりやすいので、それを中心に見ていきたいと思う。

起こりやすい置換とそうでない置換

文字列の中の1文字が別の1文字に置き換わることが置換である。編集距離の1つであるレーベンシュタイン距離では、どんな置換であっても同じコストがかかると考えている。「さ」が「ち」に変わった場合でも、「み」が「ぷ」に変わった場合でも、はたまた「槽」が「平」に変わった場合でも、距離はいずれも1増えるだけである。この辺の詳細については、以前書いた「文字列の類似度を測る(1) レーベンシュタイン距離」という記事を参照されたい。

しかし、現実には起こりやすい置換とそうでない置換がある。具体的な例を2つ挙げよう。

まず、字のかすれを考えてみよう。字がかすれることによって、本来の字とは違う字に見えてしまうことがある。例えば、本来は「に」と書いてあったのだが、「に」の左部分、つまり1画目が消えてしまったとしよう。そうすると、「に」とは認識できず、「こ」のように見えてしまう。「に」がかすれて「こ」になるようなことは、起こっても不思議ではないだろう。しかし、「に」がかすれることによって、「あ」のように見えてしまうようなことは、とても起こりそうにない。結局、字のかすれによる置換では、「に」→「こ」のように起こりやすそうな置換と、「に」→「あ」のように起こりにくそうな置換があることになる。

一般的なqwertyキーボード
一般的なqwertyキーボード

もう1つの例を考えてみよう。キーボード [1] でタイプしている場合、間違って本来打ちたいキーとは違うキーを打ってしまうことがある。例えば、“e”とタイプしようとして、“e”のキーの隣にある“r”のキーを間違って打ってしまうことは良くあるだろう。しかし、“e”とタイプしようとして、“e”のキーとは逆の位置にある“n”のキーを打ってしまうことはあまり起きそうにない。タイプミスの場合でも、起こりやすい置換とそうでない置換があるのである。

感覚的に言えば、起こりやすい置換は「近い」ものであり、起こりにくい置換は「遠い」ものであるように思われる。つまり、近くて似ているから変化が起こりやすく、遠くて似ていないから変化が起こりにくいと考えることができるわけである。そう考えると、編集を計算する場合、起こりやすい置換の場合は距離が小さくなるように、起こりにくい置換の場合は距離が大きくなるように調整した方が良さそうである。

今までは、置換はどのようなものでも同じコストであると考えてきたが、起こりやすい置換とそうでない置換があることを考えると、それではうまく行かない。起こりやすい置換の場合はコストを小さめに見積もり、起こりにくい置換はコストを高めにするのが良さそうである。もっと端的にまとめると、単純に距離を考えるのではなく、変化の起こりやすさも加味して距離を考えることが必要だということである。

変化の起こりやすさを加味したモデルはさまざまなものがあるが、DNAの塩基配列における変化についての話が分かりやすいのでそれを紹介したいと思う。

DNAについての基礎

DNAの塩基配列はA, C, T, Gの4種類の文字を使った言語である。この画像は米国National Human Genome Research InstituteのPD画像を利用した。
DNAの塩基配列はA, C, T, Gの4種類の文字を使った言語である。この画像は米国National Human Genome Research InstituteのPD画像を利用した。

話の前提として、DNAについて必要になることを簡単に紹介しておこう。なお、私は生命科学については全くの素人なので、不正確な面があるかもしれないが、その辺はご容赦願いたい。

DNA(デオキシリボ核酸)は、デオキシリボース・リン酸・塩基から成り立っている。このうち塩基はA, C, G, Tの4種類ある。

大ざっぱに言えば、この4種類のどれを採るかで生物の遺伝情報が決まってくる。要するに、DNAの遺伝情報とは、A, C, G, Tの4種類の文字で書かれる文字列として捉えることができる。

A, C, G, Tのうち、AとGはプリン塩基と呼ばれるグループに属し、CとTはピリミジン塩基と呼ばれるグループに属する。プリンからプリン、あるいはピリミジンからピリミジンに変わることを転位(transition)  [2] と呼ぶ。これに対して、プリンからピリミジン、あるいはピリミジンからプリンに変わることを転換(transversion) [3] と呼ぶ。一般的には、転換に比べて、転位の方が起きやすい。つまり、同じグループのものには変化しやすいが、違うグループのものにはなりにくい。

木村の2パラメータモデル

DNAの塩基配列における置換の起きやすさに関するモデルとして、木村 [4] の2パラメータモデル(Kimura’s two parameter model)というものを紹介しよう [5]

塩基はA, C, G, Tの4通りあるので、変化はA→C, A→G, A→T, C→A, C→G, C→T, G→A, G→C, G→T, T→A, T→C, T→Gの合わせて12通りある。一番単純に考えるのなら、この12通りのどれもが同じ確率で起こるというモデルを考えることができる。しかし、これではいくら何でも単純で、塩基配列の変化に関する実態を捉えていない。

木村の2パラメータモデルでは、転位と転換とで変化が起きる率が違うと考える。先に述べたように、一般的には、転換に比べて、転位の方が起きやすい性質がある。このため、転位と転換とを分けて考えることに合理的な理由があるのである。

なお、木村の2パラメータモデルなどに基づくDNA間の距離は、Rでは、ape というパッケージの dist.dna コマンドを使って計算できる。詳しくは、同志社大・金研究室の「[連載]フリーソフトによるデータ解析・マイニング第42回 Rと系統樹(1) 」という記事を参照されたい。

DNAの塩基配列と自然言語の違い

そもそも塩基はA, C, G, Tの4通りしかないので、変化は12通り [6] しかない。木村の2パラメータモデルでは、この12通りの変化を2種類に分けて、パラメータを2つだけにした。木村のモデルのように12通りの変化を分類せずに、各々バラバラに考えたとしても、高々12個のパラメータだけ考えれば良い。つまり、DNAの塩基配列は、使っている「文字」の種類が少ないので、モデルを作るときのパラメータもさほど多くはならない。

しかし、自然言語は使用可能な「文字」の種類がずっと多い。英語の書き言葉の例を考えると、大文字と小文字の違いを無視したとしても、文字は26通りもある。文字が26通りある場合、変化として起きうるのは650パターンもある。これをモデルにするのはなかなか難しい。いずれにせよ、確率を持ち込むしかないのだが、その辺のややこしいことは、機械学習などを通じて解決することになる。

脚注
  1. 一般的なqwertyキーボードを想定している。 []
  2. 要するに、A⇔G, C⇔Tの変化が転位。 []
  3. 要するに、A⇔C, A⇔T, G⇔C, G⇔Tの変化が転換。 []
  4. 木村資生のこと。分子進化の中立説を提唱した人。 []
  5. 元ネタは以下の論文である。 Kimura, M. (1980). A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences. Journal of Molecular Evolution 16(2), 111-120. []
  6. A→C, A→G, A→T, C→A, C→G, C→T, G→A, G→C, G→T, T→A, T→C, T→Gの12通り。 []