京都大学化学研究所 バイオインフォマティクスセンター 阿久津研究室 タンパク質間相互作用予測システム 京都大学化学研究所 バイオインフォマティクスセンター 阿久津研究室 Thank you chairman. My name is Morihiro Hayashida. I am a Ph.D student of Kyoto university. Today, I am going to talk about Inferring strengths of protein-protein interactions from experimental data using linear programming.

タンパク質相互作用 タンパク質は他の物質（タンパク質を含む）と結合（相互作用）すると、その機能が変化する。 タンパク質の役割の例として次がある。 遺伝子からのタンパク質生成量の制御 化学反応の触媒 食物からエネルギーを取り出す.

タンパク質生成の制御 DNA DNA タンパク質 プロモータ領域に 付くことが出来ない. プロモータ領域 遺伝子 タンパク質相互作用 領域に付いて, 遺伝子からの タンパク質 生成を補助する. 遺伝子からの タンパク質 生成の制御 DNA プロモータ領域 遺伝子

化学反応の触媒 タンパク質 化学反応が起きない. タンパク質相互作用 酵素として, 化学反応を促進する. NH2 O O C C H H

タンパク質相互作用の予測 タンパク質 アミノ酸配列 特徴的な部分配列

InterPro ドメイン 特徴的な部分配列として、InterPro データベースに登録してあるドメインを使用する。 ドメイン ドメイン After that, a model has been proposed. It is based on domain-domain interactions. Proteins have some domains. This model uses these domains. In this model, we can not find which residues interact in a domain. But, this makes the model simple, and we can find interactions between known domains. These domains are defined by the databases like InterPro or Pfam. This shows the result of search for a protein in InterPro database. We see that this protein holds 2 kinds of domains, this one and this one. ドメイン

タンパク質相互作用の予測 相互作用する組. 相互作用しない組. ?

タンパク質相互作用の予測 相互作用する組. 相互作用しない組.

相互作用の確率モデル (1/2) モデル (Deng et al., 2002) ２つのタンパク質が相互作用する。 少なくとも１つのドメインのペアが相互作用する。 ドメイン間の相互作用は互いに独立とする。 D3 D1 Next, I explain a probabilistic model of interaction. This model was proposed by Deng et al. They used this model when they developed EM method. Our proposed method also uses this model. Proteins consist of some domains. 2 proteins interact if and only if at least 1 pair of domains interacts. And in order to keep the probability formula simple, we assume that the interactions between domains are independent events. This figure shows this model. Protein P1 consists of domain D1 and D2. And Protein P2 consists of domain D3, D2 and D4. Same domain can be held in some proteins. Now, we assume protein P1 and P2 interact each other. Then, among domain pairs D1 and D3, D1 and D2, and so on, at least, 1 pair need to interact. On the other hand, if these 2 proteins do not interact, any of domain pairs never interact. P1 P2 D2 D2 D4

相互作用の確率モデル (2/2) : タンパク質 Pi、Pj が相互作用する事象。 : ドメイン Dm、Dn が相互作用する事象。 　　: ドメインのペア (Dm ,Dn) が、タンパク質のペア PiX Pj　に含まれる。

関連研究 入力: 出力: すべてのドメインのペアDm、Dnに対して、それらの相互作用の確率 Pr(Dmn=1)。 相互作用すると観測されたタンパク質のペアの集合(正例)。 相互作用しないと観測されたタンパク質のペアの集合(負例)。 出力: すべてのドメインのペアDm、Dnに対して、それらの相互作用の確率 Pr(Dmn=1)。

アソシエーション法 (Sprinzak et al., 2001) 相互作用するタンパク質ペアの割合より推定。 : ドメインペア (Dm, Dn) を含む、相互作用するタンパク質ペアの数。 : ドメインペア (Dm, Dn) を含むすべてのタンパク質ペアの数。 Next, I mention the related work. They inferred the probabilities of domain-domain interactions using ratios of frequencies. For each domain pair, they counted the number of protein pairs which hold the domain pair, and they use the percentage of interacting protein pairs in the total as the probability of the domain pair interacting.

EM 法 (Deng et al.,2002) 観測データ {Oij={0,1}} を上のモデルで得る確率（尤度 L）。 EM アルゴリズムを適用し、L を最大化することで、Pr(Dmn=1) を推定する。 EM method was developed using this probabilistic model. They considered the probability that experimental data Oij are observed like this. and they maximize this probability using EM algorithm. We omit the details.

Yeast 2 Hybrid 実験データ 既存の手法（アソシエーション、EM法）は、 ２値データ（相互作用するかしないか）のみを使用。 実験によって異なる結果。 Ito et al. (2000, 2001) Uetz et al. (2001) 数値データを使う手法を開発。 There are 2 methods using domain-domain interactions, this one and this one. Both methods use binary data. Binary means which a protein pair interacts or not. Ito et al. and Uetz et al. have reported their experimental results respectively. But, the number of overlapping interacting protein pairs is too small. Therefore, we have realized that using raw data for inference is better than using binary data, and we have developed new methods using numerical data.

数値データ Ito et al. (2000,2001) 同じタンパク質のペアについて、何度も同じ実験が繰り返される。 IST (Interaction Sequence Tag) 多数回の実験のうち、相互作用が観測された数。 閾値で切ることで、２値データを得ることができる。 Ito et al. performed experiments for each protein pair multiple times, and observed the number of interactions. IST (Interaction Sequence Tag) means this number. This table shows some results, and this column shows the value of IST.

提案手法 線形計画法による解法。 EM 法を数値データにそのまま応用するのは困難。 ２値データ 数値データ LPBN 組み合わせ法 SVM法 LPEM EMLP SVM法 数値データ ASNM LPNM It seems difficult to modify EM method for numerical data. Therefore, we use linear programming. Linear programming is easier to implement these problem than EM algorithm. And it is easy to add new constraints. First, we developed methods for binary data. From now, I explain these methods.

LPBN (1/2) 「相互作用する」ことの線形不等式への変換。 We developed new LP-based methods for binary data. We transform the conditions of protein-protein interactions into linear inequalities in order to obtain linear constraints. At first, we define that protein Pi and Pj interact as follows, we consider the threshold value Θ of proteins interacting. If the probability of proteins interacting is more than this value, they interact. we transpose the terms, and take the logarithm of both sides. And we replace the logarithms with variable γmn and β. Thus, we could obtain linear inequalities.

LPBN (2/2) LPBN 線形計画問題 Then, we obtain the following linear programming.

組み合わせ法 LPEM 法 EMLP 法 LPBN 法の結果を初期値として、EM 法を実行する。 EM 法の結果からあまりずれない範囲で LPBN 法の解を実行。LPBN 線形計画問題に以下の不等式制約を追加する。 I explain 2 combination methods, LPEM and EMLP. LPEM method carries out the EM method using the results of LPBN as its initial parameter values. EMLP constrains to LPBN with the following inequalities so that LP solutions are close to EM solutions. To be able to add constraints is a good point of linear programming. γEM is the result of EM. δ is a positive constant.

SVM 法 特徴ベクトル（タンパク質のペア） 線形カーネルを使う。 各要素はそれぞれドメインペアがあるかどうか。 テストデータ マージン Next, we consider the simple SVM-based method. We use feature vectors like this and simple linear kernel. マージン

タンパク質間相互作用の強度 同じタンパク質のペアについて、何度も同じ実験が繰り返される。 相互作用の強度ρij : タンパク質ペア (Pi,Pj) について、相互作用が観測された数の割合。 Kij : タンパク質ペア (Pi,Pj) について、相互作用が観測された数。 Mij : タンパク質ペア (Pi,Pj) に対する全実験回数。 We have considered about whether proteins interact or not. However, in fact, the same number of experiments for each protein pair under the same condition were performed. Then, we consider if the frequency of observed interactions is beyond a threshold, the protein pair interacts. Therefore, we consider the ratio ρij of the frequency to the number of experiments as strength. In this sense, we developed another linear programming.

LPNM (1/2) タンパク質ペアが相互作用する確率 Pr(Pij=1) と強度ρij の差を線形計画法を使い最小化する。 This linear programming minimizes the gap between the probabilities of domain-domain interaction and the ratio ρij. We transform the formula as before.

LPNM (2/2) LPNM 線形計画問題 Thus, we obtain this linear programming. αij means the value of the gap. Here, βij is a constant value from experimental data.

ASNM ２値データ用のアソシエーション法を数値データ用に修正。 ２値データ(Sprinzak et al., 2001)では、 We also developed Association method for numerical data in order to compare the LPNM method.

２値データに対する計算機実験 DIP データベース (Xenarios et al., 2002) 計算機環境 タンパク質のペア 1767 個を正例として使用。 学習に 2/3 、テストに 1/3 を使用。 計算機環境 Xeon 2.8 GHz 線形計画問題の求解に使ったプログラム: loqo We conducted computational experiments to verify the proposed methods. We used DIP database like this. and the computational environment is in the screen.

学習データについての結果（２値データ） EM Association LPBN SVM This is the result on training data. This shows ROC graph, It shows that larger the left-down area of the curve is, better the method is. It is seen from this figure that EM method is better than other methods.

テストデータについての結果（２値データ） EM EMLP LPEM SVM Association This is the result on test data set. It is seen from this figure that EMLP is slightly better than EM method.

数値データに対する計算機実験 YIP データベース (Ito et al., 2001, 2002) 計算機環境 IST (Interaction Sequence Tag) タンパク質のペア数：1586 学習に 4/5 、テストに 1/5 を使用。 計算機環境 Xeon 2.8 GHz 線形計画問題の解法器: lp_solve We also conducted computational experiments for numerical data. we used YIP database. I introduced a part of this data set on a previous slide. Computational environment is in the screen.

テストデータについての結果（数値データ） ASNM LPNM EM Association This is the result on test data set. This figure represents the distributions of the errors between experimental data and predicted probabilities. The errors of LPNM and ASNM concentrated around 0. But this figure shows LPNM was better. That is, LPNM minimizes the errors successfully.

テストデータについての結果（数値データ） LPNM 法で最良の結果。 EM 法、アソシエーション法は Pr(Pij=1) を 0か1に分類しようとする。 LPNM ASNM EM ASSOC 平均誤差 0.0308 0.0405 0.295 0.277 CPU 時間（秒） 1.20 0.0077 1.62 0.0088 This result is also on the test data. We calculated the averages of the errors. LPNM is better than ASNM, and much better than EM and Association methods. These results are reasonable because EM and Association methods classify the probabilities of proteins interacting into either 0 or 1.

理論的成果 問題 完全に分離できるなら多項式時間。 完全に分離できない場合はNP困難。 良い近似を得ることも困難（MAXSNP困難）。 「正例のうち、　　　　　　　　　　　　　　を満たす　　の個数＋ 　負例のうち、　　　　　　　　　　　　　　　を満たす　　の個数」を最大化。 完全に分離できるなら多項式時間。 完全に分離できない場合はNP困難。 良い近似を得ることも困難（MAXSNP困難）。

まとめ タンパク質ペア間の強度を予測する問題を提案し、線形計画法による解法を開発した。 提案手法 2値データ 数値データ LPBN, LPEM, EMLP SVM法 数値データ ASNM LPNM LPNM で良好な結果を得た。 I summarize our study. We defined new problem to infer strengths of protein-protein interactions And, we proposed LP-based methods for inference of protein-protein interactions. LPNM outperformed existing methods.

タンパク質間相互作用予測システム ドメイン間相互作用の確率 Pr(Dmn=1) を上の各手法を使って推定。

タンパク質名 （swissprot データベース） タンパク質に含まれるドメイン名 （InterPro データベース） タンパク質のアミノ酸配列 （FASTA 形式）

Flavocytochrome B2 (P00175)

P00175 との相互作用確率の 推定結果

大学院生募集（修士、博士） 京都大学大学院 情報学研究科 知能情報学専攻 バイオ情報ネットワーク分野 入試 ２００４年２月（博士） ２００４年８月（修士、博士） 専攻のホームページ http://www.i.kyoto-u.ac.jp/~ist/index.html 研究室ホームページ http://www.bic.kyoto-u.ac.jp/takutsu/index_J.html 研究室の見学を随時受付けています。 E-mail : takutsu@kuicr.kyoto-u.ac.jp