125

数理解析研究所講究録
第1186巻 2001年 125-132

遺伝情報学におけるセグメント法を用いたマルチプルアライメント

東京理科大学大学院大矢研究室 村松重人 (Shig.e.to Muramatsu)
東京理科大学理工学部情報科学科

対象としたアライメントをマルチプルアライ

1.はじめに遺伝子の DN A(デオキシリボ核酸) は4種類の塩基, A(アデニン),G

大矢雅則 (Masanori Ohya)(グアニン),CT

メントという.

一般にペアワイズアライメントのアルゴリ(チミン),(シトシン) で構成され,ズムでは, 全てのギャップの入り方を考慮しさらて計算するが, マルチプルァライメントでギにタンパク質は20種類のアミノ酸で構成さャップの入り方を全て考慮すると, その計算れている. この1次元のデータを解析し, そ

コストは配列の長さを L , 配列の本数を N とアミノ酸はこの4種類の塩基からなり,のデータを用いて生物の進化系統樹を作成すしたときに O(L^{N}) となり, アミノ酸配列の本る. また, 直接このデータを比較することに数の指数関数的に増えてしまい事実上計算不より, 生物間における共通の部分を見つけだ可能となる. そのため, マルチプルアライメし, 構造や機能の推定をすることが可能となる. この1次元のデータの解析を行う際 (特ントにおいては, ギャップの入り方の全てについては考慮しなくて済むアルゴリズムが必にアミノ酸において), まず最初に行わなけれ要となる. そのため, シミュレーテッドアニばならない操作がアライメントであり,一リングを用いた方法 [3] などが知られていこれは, 配列を観察しやすくするために, 各アミる.

ノ酸間にギャップ (配列の—部が失われたり,新たな断片が入り込んだことに対応するも2 シミ \iota レーテッドアニーリングを用いたマの) を挿入し, もとのアミノ酸配列の順序をルチプルアライメント保存したまま配列を並び換える操作である.

この節では, 組み合わせ最適化問題で用い

例えば, 次のような生物A, \mathcal{B} の同じ機能をられるシミ 2_{\wedge} レーテッドアニーリング [4] に持つタンパク質におけるアミノ酸配列についついて簡単に述べ, それを用いたマルチプルてみてみることにする.

アライメントについて説明する.

A : MN PQYS TWQ\mathcal{B} : MN PQYT VW PY
このA と \mathcal{B} の間に進化の過程に於いて, アミ

いま, Xを空でない有限集合とする. 有限YT集合X の要素を基本状態と呼ぶ. そして, 有限集合X上の実数値関数

f:X\vdash\Rightar ow \mathfrak{R}ノ酸の変化 (置換, 欠落, 挿入) が起こったとする考え方が妥当である. そのため, その変化の場所に*(ギャップ) を挿入してみる

ミと,A : MN\mathcal{B} : MN PQY*T VW PY*となり, A と \mathcal{B} の類似性が視覚的に捉えるこPQYST*WQYTとができる.

を考える. この関数f を目的関数と呼ぶ. このとき f を最小にする X の要素 (状態) をシ

このように, 特に2つのアミノ酸配列を対象としたアライメントをペアワイ

ズアライメント,3本以上のアミノ酸配列をz_{\sim}

レーテッドアニーリングを用いて求める.

まず, X上でのfの最小値を f_{\min} とし, f_{\min} を与える X の要素の集合を X_{\min} と定義する.
[定義2‐1]

f_{\min} \equiv\min\{f(x)|x\in X\}

X_{\min}\equiv\{\chi|_{X}\in X\cdot,f(X)=f_{\min}\}126

次に, 確率分布q0 (X) を次のように定義する.
このq0は最適分布と呼ばれる. この最適分布になるように各アミノ酸配列の後ろにギャップを発生させることができれば,を挿入して配列の長さを等しくする. 次に, ア

f を最小にすノ酸を表す. 最長のアミノ酸配列の長さと同じライメントを行うために十分な数のギャップをる X の要素を求めることができる.

追加する.

[定義2‐2]p_{0}(_{X})\equiv\{
ただし,\frac{1}{|X_{\min}|0

A_{1} : a_{t}^{1}a_{\underline{7} \cdots a_{\l corner}^{1}|(x\in x1nin)

A_{2} : a_{1^{0\cdot\cdot a}\sim}^{2 .2}?\l corner(その他)|X_{\min}| は x\in x_{mi\mathfrak{n} となる

x

A_{n} : a_{\iota}nn\ldots na2a_{1}.の個数でそして, 正のパラメータ \beta と X上の関

アミノ酸配列を計算機で摂動させるためには,

数f を用いて関数pβ(x) を次のように定義すそのままの状態では困難なため, アミノ酸配る.

列のアミノ酸を “ 1 ”, ギャップを “ 0 ” とし[定義2‐3]て数列に置き換える. 例えば以下のようになある.

る.

\forall x\in X.\cdot.

p_{\beta}(x) \equiv\frac{1}{Z}\exp\{-\beta f(x)\} (\beta\geq 0)

A_{1} : MNPQ**arrow A_{1} ’ :111100
A_{2}' : 111000
A_{2} : MPQ***

Z \equiv\sum_{\in x\chi}\exp\{-\beta f(X)\}

この数列に対して摂動を行い摂動済みの配列

この p_{\beta} を, パラメータ \beta におけるギブス分布を得る. 具体的には, 無作為に選択した数列と呼び, このギブス分布と最適分布の間には,(アミノ酸配列) の, 無作為に選択した要素“ 1” (アミノ酸) と, “ 0 ” (ギャップ) を交次の定理が成り立つことが知られている.

換する. 例えば,

A_{2}^{\dag er} の2番目の “ 1 ” と1番後ろの “ 0 ” が選択されると,< 定理 2- 1>\lim_{\betaarrow\infty}p_{\beta}(x)=p_{0}(X)
このことより,\beta を十分大きくすれば,ギブ

A_{1}' : 111100
A_{2}' : 101001

arrow A_{1} : MNPQ**
A_{2} :M*P**Q

ス分布は最適分布に収束することが分かる.

次に, シミ=-レーテッドアニーリングを用いとなり, 摂動を行ったアミノ酸配列が得られたマルチプルアライメントについて説明する.

る.

まず, 一般的に 本のアミノ酸配列A1から A_{n}的関数としては,を以下のように定める.

るが, ハミング距離をベースとした次の式がnこの配列に対して目的関数を求める.

A1:a^{11.1}1a\cdot\cdot a2k_{l}A_{2} o_{l}^{22}a2\ldots a_{k_{2} ^{2}

ある.

A_{n} : a^{n}a_{2}^{n}l\ldots a_{k_{n} ^{n}ただし,

ここで, a_{j}^{i} はアミノ酸配列A, の j 番目のアミ

さまざまなものが考えられ

f(x)=\sum_{k=}/.1=\sum_{j\iotaj=}^{-}\sum_{j+\iota}\frac{d(a_{k}^{j},a^{j})k} {n2C}n1n

:

目

127

d(a_{k},O_{k}j)=\rflo r_{1}^{0}(_{0_{k}^{\iota_{k} =(0^{j}\neqa^{j}\ovalbox{ \t smal REJ CT}>つa^{J})k (a\neq*\ovalbox{\t smal REJ CT}\ovalbox{\t smal REJ CT}つa^{j}\neq*)jk )a_{k}^{J}\ovalbox{\t \smal REJECT}>\prime\supset(a_{k}^{\iota}=*ま\ovalbox{\t \smal REJECT}_{c}\ovalbox{\t \smal REJECT}\upar ow\ovalbox{\t \smal REJECT} a_{k}=J*)とする. ここで,wの分布はアミノ酸ごとにある領域に限定されている.

この回転角(\phi, \phi) をそれぞれ縦軸横軸方向にプロットした図をラマチャンド
ランプロットと呼ぶ.

はギャップの重みを表し,一般的に2.0と取られることが多い.
この目的関数からその摂動を受理するかどうか判断する. 受理する場合には摂動済みの状態を, 受理しない場合は摂動前の状態を採用する.

この操作を受理行列の \beta の値を大きくしながら繰り返すことによって, アライメント結果を得る.

3. 目的関数の補正2節に述べた目的関数においては, 例えばA(アラニン) が G (グリシン) に置換されても,P

図3.1 タンパク質の主鎖の二面角(プロリン) に置換されても, その置換におけるアミノ敵同士の距離は1であり,違いが現れない.

しかし, 実際にはそれは不自然なことであり, タンパク質を形成する20 種類のアミノ酸は任意の形をとれないことから, この節ではうマチャンドランプロット
を用いてアミノ酸同士の距離を求めアライメントの目的関数に利用する方法を述べる.
タンパク質の主鎖を構成する結合部分は様々な角度に折れ曲がっており, 多くのコンポメーションをとる. C_{\alpha}-C 結合, C_{\alpha}-N 結合及び C-N 結合のまわりの3箇所で回転することができるということになる.
\omega

図32 グリシンのラマチャンドランプロット

しかし,はペプチド結合の二重結合性の問題や側鎖2つのアミノ酸の角度分布を用いてエントロのぶつかりを避けるために \pm 180 度程度のピー進化率を計算し, 正規化したものを距離と値とることが多い. このことよりタンパク質する.の主鎖の構造は,エントロピー :\phi と \phi の2つで記述することができる. そのためにとを二面角という.

\omega(\phi, \phi, \omega) のこ

S(a)=-\sumj=NIj\sum_{\iota=}^{N}\frac{n_{j}^{a}j {N_{a} \log\frac{n_{j}^{a} {N_{a}が固定されているので,C_{a} の両側に2枚の平面がありその回転角が\phi と \phi であると考えることができる.

この二S(b)=-\sum_{1i=j}^{N}\sum\frac{n_{j}^{b}j{N_{b}N=l.\og^{\frac{n_{j}^{b}j {N_{b}

つによってタンパク質の主鎖の立体構造が決定されている. 実際には主鎖と C_{a} に付随する測鎖の間には立体的な障害があり, 許される
C_{a}-N 結合まわりの回転角 \phi ,相互エントロピー :C_{a}-C 結合まわりの回転角 \emptyset の値は制約されるため, そI(a,b)=\sum_{1i=}^{Nx}\sum_{=j1}^{N}\gam a\log^{\frac{r_{j} {p_{ij}q_{j} NxNj

128

ス,

対称エントロピー比 :r(a|b)= \frac{I(a,b)}{S(a)}i\cdot:.

\beta- シートなどの2次構造があげられる.

そのため, このようなアミノ酸については,優先して合わせてからアライメントを行えば,同じ位置に揃いアライメント結果を補正できr(a,b)= \frac{\{r(_{0}|b)+r(a|b)\} {2}

ると考えられる. この節ではその方法について説明する.

固定するアミノ酸の位置を縦に揃えて摂動

d'(a,b.)=1-r(a,b)

させるために, 固定するアミノ酸の前後に存そしてこのアミノ酸間の距離行列を用いて次在するアミノ酸とギャップの数が変化しないのように目的関数の補正をする.

ようにする

エントロピー進化率 :.
-d(a_{k}^i,a_{k})j=1^{}0(a^{\iota}=)k +\alph(a^{i}\neqa\ovalbox{\t smal REJ CT}j*\ovalbox{\t smalREJ CT}1つ0^{i}\neq1つa_{k}^i\neq*)ktd|(a_{k} ^{i}a_k}j')-\beta\}|w ( a_{k}^{\iota}\neq a^{j}kか^{つ}(a_{k}=まl* た#Si a_{k}^{\iota}=)* )ここで, 0\leq\alpha,\beta\leq 1 であり,\alphaは角度による距離の影響の大きさを決定するパラメータで,その値が大きいほど影響は大ぎくなる.

\betaはY

図4.1摂動の方法

角度による距離ぶアミノ民間の距離をどのよ\overline{q}. \sim- タで , そのよって, 固定するアミノ酸の前後のアミノ1に近いほど近酸配列には別々のギャップを挿入し, それらうに見せるかを決定するパラメ

値が 0 に近いほど遠く見せ,. . \wedge. -.' .

く見せる.

を別々のアミノ酸配列と見なしアライメント\cdot..

を行えば良いということになる. 例えば, 次4対応する部分を固定するアライメント.::

タンパク騨は, ある原子団岬互作用しのようなアミノ酸配列があったとする.

たり, タンパク質の構造を安定にする役割を

A :T KTY P PHFD LS HG S A担ったりする重要な役割を果たす部分が存在\mathcal{B}T KTY P P HD L\underline{S} HG S A

する. この部分に当たるアミノ酸は, ある固C : QRF\underline{P}Esp GD LSPD A

有の機能を実現するための特定の性質を持っ

D:QRF\underline{P}Esp GD LSTPD Aたものでなければならない場合がある.

\mathcal{E} : RF\underline{P}ESFGD LS TADAV

もし:

この特別な役割を果たしている部分のアミノ酸が, 欠落したり, 他のアミノ酸に置換され

ただし,てしまうと, その生物は正常な生体反応を維いるアミノ酸が構造保存部位で, あらかじめ持できなくなり, 長期間生存することができ固定を行う部分だとする. すると, 最初に固なくなる可能性がある. 現在生存している生.

=..\backslashこのアミノ酸配列の下線の引かれて定する部分で区切られた各アミノ酸配列に必物, あるいは化石として発見される生物は,要なだけのギャップを挿入する. また, 対応ある程度の期間にわたって生息した生物であが分かっていないアミノ酸配列 (ここでは,るから, そのような重要な部分にあたるアミC の後ろの部分) についても, 初期状態でアノ酸は, 進化しても保存される力↘ 似たようミノ酸の対応が大きくくずれないように, 同な性質のアミノ酸に置換されているかのいず様にしてギャップを挿入する.

C のみが2本れかと考えられる. このような, 重要なアミの配列として扱われ, その他の A, \mathcal{B},ノ酸の部分には構造保存部位や α.ヘリック\mathcal{E} については,D,3本の配列として扱われ全部

129で14本の配列と見なせる. この状態を初期状態としてアライメントを行うと,14本の∼固定なし

w-構造保存部位—2次構造−*—両方配列からランダムに1本の配列を選び摂動を加え,目的関数を計算することができる.

長さが異なる小さな配列への摂動の振り分けかたとして, 今回は, 初期状態においてそれぞれの配列のギャップの入り方の総数に比例した確率で摂動を振り分ける. N本のアミノ酸配列のうち, i 番目のアミノ酸配列に摂動が割り振られる確率pl は, 次のようになる.
’p_{i}= \frac{(l_{j}+m_{j}{}_{)}C_{m_{i} }{N}\sum_{k=1}(/+kmk)Cm_{k}図42固定別による収束状況の相違

ただし, l_{i},m_{i} は, それぞれi番目のアミノ酸配列に含まれるアミノ酸の数とギャップの数である.

ループ回数..

5固定するセグメントの検出
3節の特殊なアミノ酸の部分を考慮してアライメントを行う方法では, アライメントをアニーリングアライメントにおいては, ギ行う前に固定するアミノ酸が複数のアミノ酸

ャップの入り方の総数が少ないと解が求めや配列に対して判っている必要がある. しかし,すい. そのため, この方法により, 構造保存アライメントを行う段階において必ずしも,部位を考慮しない場合に比べギャップの入りそのような位置がわかっているとは限らない.

方の総数を減らすことができ, 解が求めやす

特にシーケンスアライメントの場合はタンパくなる. 実際に, アミノ酸配列にアミノ酸が lク質の立体構造がわかっていない場合に行わ個, ギャップが m 個, 対応する部分が n 個あれるので, そのような場合には上記のアルゴるとする. このとき, 対応する部分を考慮にリズムを適用することができないことがある.

入れない場合,ギャップの入り方は_{}()c_{n}1+mt 通

そこで, 固定するセグメントを検出する方法について述べる.

りとなる. これに対して, 対応する部分を考次のような配列を例にしてマルチプルアライ

慮に入れるとギャップの入り方は最大でもメントアルゴリズムを説明する.

(l+m-n)cm 通りである. また, この配列は n+1本の独立な配列と見なせるので,A

GF I:

L A TP AAAA FCQKLQ I

i 番目\mathcal{B}:YSHF AAA B I(i=1,2, \cdots,n+1) の配列におけるアミノ酸のC:

GVMF A TTLAAB AMD V T

QEFL A RW

数を l_{j} 個, ギャップの数を m_{j} 個と置くと, ギ

アミノ酸配列の中からどれか1つを選択し,ャップの入り方は,選んだ配列中の任意の位置から連続するいく\square(/+m)C_{m_{j} \primel+1j=1li (= \sum_{jl}^{n+l}l=l-i\sum_{j}^{1}n,m=m)n+=|j

つかの配列を選択し, 部分配列 (セグメント)とする.

この際, どの位置の連続数個を選択するかは,である. . これらより, あらかじめ対応する部色々と試行してみる必要がある. 対象となっ分を考慮に入れたアライメント方法の方が最ている部分配列に対して, 対象となっている適値により早く収束するということが言える.

配列以外の配列と総当たり的に距離を計り,130

最小となる部分を検索する.
A :

GF

I

L A

TP.A\ovalbox{\t \small REJECT}AR FCQKLQ I

A

GHAGEYGAEALER\mathcal{B}

GHAAEYG**A***C

NVD*EVGcEALGR

選択.\cdot.\cdot. \cdot.\cdot.\cdot.\cdot:.\cdot.\cdot.\cdot\dot{.}\dot{\overline {8} \cdot.\cdot\cdot.f\wedge-\ovalbox{\t \smal REJECT}

しかし, 総当たり的に距離を計るためにセグメント検索するとき, 最初に対象としたセグメントの位置とあまりにかけ離れた位置にヒ\mathcal{B}6^{:}

ットしてしまうことがある. このとき, アラボ\}A\mathcal{B}C

イメントを行い得られた結果が以下の通りで:ある.

P響広量圏F: YSHF.=A\ovalbox{\tt\small REJECT} I QEFL A RW
: GVMF A TTL.\cdot\ovalbox{\tt\small REJECT} DvT
GFlLAT

9\circ QKLQ1

A\mathcal{B}CA\mathcal{B}C

P*:\ovalbox{\tt\small REJECT}^{pcQKL}Q1*: YSHF****.A\ovalbox{\tt\smallAAC
REJECT} I QEFL ARW: G VMFAT TL.\cdot.\ovalbox{\tt\small REJECT}_{M}DvT****;GF IL AT:\cdot

19

検索でヒットしたセグメントを固定しギャップを補充する. これによって1つのアミノ酸配列が2つのパートに分けられる.

V*LSP****A***D**KS.\cdot.r
v*LSA****A***D**Kc\aleph m\ldots\ldots\cdot: V HLTPEEKN AV TT LWG K V.$:

12A

VK..\cdot.\cdot\dot{\overline{\ddot{\dot{A}}}}.\cdot..|AwcKVccHAcEYGAEA

C\mathcl{B} VK.\cdot.\cdot.\cdot.\cdot.\cdot.\cdot.\cdot.\cdot.\cdot. \dot{\d ot{\d ot{\dot{A} vD.\d ot{\d ot{\d ot{E} \infty^{\overline{1}W. \cdot.\cdot.\cdot.\cdot.\cdot. \cdot.|v*cA KVc* GH* AE*A E*
22A

LER

このアミノ酸配列に対して, シミ 2‐ レーテッ

\mathcal{B}

YGA

ドアニーリングを用いたアライメントを行う.

CLGR

6検証実験と考察

まず, 以下のデータを用いて5節のアライメ

結果は好ましくないものとなってしま \ovalbox{\tsmalREJCT}\ovalbox{\tsmalREJCT} ,ントを行ってみる.

その原因は固定するセグメントが最初に指定したものと比べて上記のように大きく離れた

A : V LSP A DKSNV KAAWG KVGG
\mathcal{B} : V LSAADKGNv KAAWG KVGG

位置が固定するセグメントになってしまうことにあると考える. そこで, 固定するセグメ

VHLTPEEK NAV TT LWG KVN

ントを検索する際に, 次の方法で距離を計算

C :し, 離れた位置にあるアミノ酸に対してペナAHAGEYGAEALER\beta

HAAEYGAC . VDEVGGEALGRルティーをもうけることとする.

比較するアミノ酸をそれぞれ a,わとする.

d(a, ,わのは今までと同様にアミノ酸間の距離
l は区間の長さとする.

すると, 最適解は次のようになる.

また,

pa,pb はそれぞれのアミノ酸が前からの何番目かを表すものとする.

A:

V*LSP A

D.\cdot. \ovalbox{\t \smal REJECT} sNVKAA.\cdot.\cdot\ovalbox{\t \smal REJECT} GKVG

C\mathcl{B}\prime\prime.V*L HTsA pED.\cdot.\cdot.\cdot.\cdot.\cdot.\cdot. \cdot.\S cdot.\dot{\dot{\dot{\dot{\dot{\dot{\dot{\dot{\dot{\sigma} }\ovalbox{\t smalREJCT}.\cdot.\cdot.GNVKA .\cdot\cdot.\cdot.\cdot.\cdot. \cdot\valbox{\t smalREJCT}_{GKVc|NAVTL\ovalbox{\t smalREJCT}_{cKv*0(a=b)

s(a,b)=\{ 1+d(a_{j},b_{j})+ \frac{(p_{a}-p_{b}(}{l}(a_{j}\neq b_{\dot{j} )131

離れた位置に出現するアミノ酸に対して重みA : IVGGYKCEKNSQPWQVAVINEYLCGGVLIDPSをつけることによって, 妥当なアミノ酸列を\mathcal{B} : IVGGQECKDGECPWQALLINEENEGFCGGTILヒットさせることができる.

C

実験は次のデータを用いて行った.

D : IVNGEEAVPGSWPWQVSLQDKTGFHFCGGSL: VVGGTEAQRNSWPSQISLQYRSGSSWAHTCG\mathcal{E}: IVGGYTCGANTVPYQVSLNSGYHFCGGSLINS\mathcal{B} : V LSP A DKSNVK A AWcKvGGAWVITAAHCYSNNYQVLLGRNNLFKDEPFAQC: V LS AA DKGNVK AAWG KVGG

\mathcal{B}SEFYILTAAHCLYQAKRFKVRVGDRNTE QEE

D : V HLTPEEKN AV TTLWGKvNCGTLIRQNWVMTAAHCVDRELTFRVVVGEHN\mathcal{E}DINENWVVTAAHCGVTTSDVVVAGEFDQGSSA: V LSP A DKTNVK AAWG KVG A: V HLTPEEKs AV T A LWGKVN\mathcal{F} :MLT A EEK AAV T A FWSKVHV\mathcal{E}QWVVSAAHCYKSGIQVRLGEDNINVVEGNEA

H A GEYG A E A

LERMFLsFpT\mathcal{B}

GGEA\mathcal{B}H A GEYG A E A

LERMFLsFpTC

LNQNNGTEQDSEKIQ\mathcal{E}Q

C

H AA EYG A E A LERMFLsFpTDV DEVGGE A\mathcal{E}V DEVGGE A LGRLLVVYPW\mathcal{F}DEVGGE A LGRLLVVYPWLGRLLLvYPw

アミノ酸配列2アミノ酸配列1固定されるセグメントは以下のようになる.

GEYG.\cdot\ovalbox{\tt\small REJECT}_{ER}MFLsFpT\mathcal{B}HAGEY G羅羅翻E RMFLSFPTCHAAEY G璽羅翻E RMFLSFPTDVDEV GOコエG RLLLVYPWVDEV GECロコG RLLVvYpw\mathcal{E}\mathcal{F}DEV G二二翻G RLLVVYpw
A

HA

アミノ酸配列1の固定するセグメント

O

hhbハC

LNQNNGTEQDSEKIQ\mathcal{E}Q① , ②: 固定するゼグメント①’: 補正前の目的関数による D セグメント①アライメントを行うとそれぞれの目的関数の収束状況は図6. 1, 図62の用になり, セグメントを固定してアライメントするとその収束

132が早くなることが見て取れる.

しかし, 指定するセグメントの位置と長さが問題で, アミ\sim

ノ酸配列の端寄りのセグメントを指定した場

E定なし

一n— 固定 (37,43)

E 定 (2,7)-*- 固定(2,7,37,43)

合と, 中央寄りのセグメントを指定した場合とでは, 後者の方がギャップの入り方の組み合わせが少なくアライメントの効率も上がる

ため, 最初に指定したセグメントがどの位置にあるかが問題である. また, 最初に指定するセグメントの長さが短いとそのセグメントに対して検索でヒットするセグメントの候補が多く存在することになり, 妥当性の低いものもヒットしゃすいと考えられる. 逆に最初

ループ回数に指定するセグメントの長さが長いとアライメントにおける摂動の自由度が小さくなり固定するセグメントが邪魔をして目的関数の最図62 アライメント 2の収束小値が大きくなってしまうことが考えられる.

そこで,4節でのアライメントの方法では複数のアミノ酸配列に対して何らかのタンパ文献ク質め立体構造がわかっている必要があった[1] Ohya M. and Uesakaが, 例えばアライメントを行いたいアミノ酸Sequences

and配列に対して,1つでもその2次構造がわかMatching^{\mathfrak{j}}',Informati_{0}nっている場合,( Brookheven Protein Data63, pp . 139‐151 (1992)

Bank などで検索可能) その特徴的な構造の部

Y.:^{||}AminoAcidDP’Science[2] Ohya M. and Miyazaki S. and Ohshima

分はアミノ酸の連続であり, ほかのアミノ酸Y.: ” A

配列にもその部分と相同性の高い部分がある

Amino Acid SequenCes\dagger\dagger,ViVa Originoと考えるため, その部分をセグメントに指定してアライメントを行うとよいと考えられる.

[_{-E定}^{\overline{\simE定\prime_{d^{\backsla h}\cdotb,E}\overline{定} \underline{.\cdot.\cdot\cdot(12 6)-*E}\underline{定(26 ^{-}9)1W\cdot-(2,5)

new method of alignmentof

17, pp .139‐151(1989)[3] Ohya M. and Miyazaki S. and Ogata
K.:^{\dagger\dagger}On Multiple Alignment of Genome
sequenceSI\mathfrak{s}\dagger,EICE6,PP^{453}.‐457(1992)[4] Aarts E. and Korst J.:^{\dagger\dagger}simulated
Annealing

andBoltzmann

Machines,J||ohn Wiley and Sons(1989)[5] M.Ohya;

Information

theoreticaltreatment of genes, The bans. of theIEICE,Vol. E72,No.5,pP\cdot 556 ‐560(1989)[6] 三宅成樹金久實;” ヒトゲノム計画と知識情報処理”,培風館(1995)
1.

\delta\cdot

B..

g1 II O

ループ回数

図6. 1 アライメント 1の収束

1 U