位置依存スコア行列の

例からの推定について阿久津達也takutsu@kuicr.kyoto-u.ac.jp京都大學化學研究所バイオインフォマティクスセンター位置依存スコア行列の

例からの推定について阿久津達也1位置依存スコア行列位置依存スコア行列2スコア関數推定問題の定義入力正例:X1,X2,X3,…負例:Y1,Y2,Y3,…出力：以下を満たすスコア関數X1,X2,X3,…は最適(もしくは、しきい値以上)Y1,Y2,Y3,…は非最適(しきい値以下)スコア関數推定問題の定義入力3スコア関數推定に関する理論的結果最適化/同定スコア関數の學習ペアワイズアライメントPP

(ICALP98)マルチプルアライメントHardHard

(ICALP98)RNA二次構造予測PP

(ICALP98)タンパク質スレッディングHardHard

(ICALP98)疎水性指標PP

(new)位置依存スコア行列PHard

(new)混合分布PHard

(new)スコア関數推定に関する理論的結果最適化/スコア関數の學習ペア4位置依存スコア行列の推定入力:POS(Σ上の文字列集合、正例)NEG(Σ上の文字列集合、負例)L(モチーフ領域の長さ)出力:PSSMf

としきい値

Θs.t.ForallSinPOS,thereisasubstring

S’ofSforwhichf(S’)>=ΘForallSinNEG,forallsubstringS’ofS,f(S’)<Θ位置依存スコア行列の推定入力:5位置依存スコア行列位置依存スコア行列6PSSM,Score,LinearInequalityPSSM:f(S)f(S)=Σfi(S[i])where

S=S[1]…S[m]Xi,a=fi(a)

,S=TGCとするとf(S)>=Θは

X1,T+X2,G+X3,C>=Θ?モチーフ領域が既知なら線形判別により簡単PSSM,Score,LinearInequality7NP-困難さの証明NP-hardifLisnotbounded(|Σ|=2)Reductionfrom3SAT3SAT:C={c1,c2,…,cn}overX={x1,…,xn}S(i,j,…):stringoflength4n

S[i]=1,S[j]=1,…?S[k]=0fortheotherpositionhNEG={S(),S(4n),S(i,j),S(i),S(2i-1,2i,4n)}POS={S(g(i1),4n)?S()?S(g(i2),4n)?S()?S(g(i3),4n)}forclausec=li1orli2orli3whereg(ik)=2ik-1ifli1ispositiveliteral,otherwiseg(ik)=2ikNP-困難さの証明NP-hardifLisnotb8位置依存スコア行列の-例からの推定について課件9Lを固定した場合の多項式時間アルゴリズムConstructanarrangementofhyperplanesin(|Σ|L+1)-dimensionalEuclideanspaceforthehyperplanes:Θ=f(S’)foreachsubstringS’oflengthLofeachsequenceinPOSUNEG

CheckeachcellinthearrangementApplicabletoderivationofhydropathicindicesbecausef1=f2=…=fL.Lを固定した場合の多項式時間アルゴリズムConstruct10ArrangementofHyperplanesCombinatorialandComputationalComexities:O(nd)fornplanesind-dimensionsThesignofy-fi(x)doesnotchangewithineachcellArrangementofHyperplanesComb11Lを固定した場合の補足Σ、Lを固定した場合、考慮すべき文字列の個數は定數個?多項式時間はtrivial位置に依存しないスコア行列（例えば、疎水性指標）の場合は、文字列の個數は定數個では無い（スコア行列のサイズはΣ）疎水性指標の學習：通常は膜貫通領域などのモチーフ領域が既知今回の結果はモチーフ領域が既知で無くても推定可能を示唆Lを固定した場合の補足Σ、Lを固定した場合、考慮すべき文字列12PSSMのMixtureの學習入力:POS,NEG,N(#PSSM)ただし全ての配列は同じ長さ出力:以下を満たすN個のPSSMの組(f1,…,fN)とΘPOS中の全ての配列Sについて、あるPSSMfk

が存在し、fk(S)>=ΘNEG中の全ての配列S,全てのPSSM

fk

について、fk(S)<ΘPSSMのMixtureの學習入力:POS,NEG,13PSSMの混合分布の幾何的解釈PSSMの混合分布の幾何的解釈14PSSMのMixture學習についての結果N=1,およびN=|POS|の時は多項式時間アルゴリズムが存在N=１の時は、以下の線形計畫問題に帰著f(S)>=ΘforeachSinPOSf(S)<ΘforeachSinNEGNが（２以上の）定數の時は、NP困難PSSMのMixture學習についての結果N=1,および15アラインメントスコアの學習入力正例:同一ファミリー內の配列ペア(Xi,Xi’)不例:異なるファミリー內の配列ペア(Yi,Yi’)出力：以下を満たすスコア行列および閾値Θscore(Xi,Xi’)>=Θ、score(Yi,Yi’)<Θ既存手法頻度に基づく(PAM、BLOSUM)最適化に基づく手法(Goldstein,蓬來)問題點：シードとなるアラインメントが必要結果文字數（殘基數）に制約が無い場合は、NP困難アラインメントスコアの學習入力16PSSMに関するまとめPSSMのサイズが固定?多項式時間固定でない?NP困難2個のPSSMのMixture?NP困難課題実用的なスコア行列推定法の開発學習データに対する分類エラーの最小化←実際には「実行可能解無し」がほとんどPSSMに関するまとめPSSMのサイズが固定?多項式時間17位置依存スコア行列の

例からの推定について阿久津達也takutsu@kuicr.kyoto-u.ac.jp京都大學化學研究所バイオインフォマティクスセンター位置依存スコア行列の

例からの推定について阿久津達也18位置依存スコア行列位置依存スコア行列19スコア関數推定問題の定義入力正例:X1,X2,X3,…負例:Y1,Y2,Y3,…出力：以下を満たすスコア関數X1,X2,X3,…は最適(もしくは、しきい値以上)Y1,Y2,Y3,…は非最適(しきい値以下)スコア関數推定問題の定義入力20スコア関數推定に関する理論的結果最適化/同定スコア関數の學習ペアワイズアライメントPP

(ICALP98)マルチプルアライメントHardHard

(ICALP98)RNA二次構造予測PP

(ICALP98)タンパク質スレッディングHardHard

(ICALP98)疎水性指標PP

(new)位置依存スコア行列PHard

(new)混合分布PHard

(new)スコア関數推定に関する理論的結果最適化/スコア関數の學習ペア21位置依存スコア行列の推定入力:POS(Σ上の文字列集合、正例)NEG(Σ上の文字列集合、負例)L(モチーフ領域の長さ)出力:PSSMf

としきい値

Θs.t.ForallSinPOS,thereisasubstring

S’ofSforwhichf(S’)>=ΘForallSinNEG,forallsubstringS’ofS,f(S’)<Θ位置依存スコア行列の推定入力:22位置依存スコア行列位置依存スコア行列23PSSM,Score,LinearInequalityPSSM:f(S)f(S)=Σfi(S[i])where

S=S[1]…S[m]Xi,a=fi(a)

,S=TGCとするとf(S)>=Θは

X1,T+X2,G+X3,C>=Θ?モチーフ領域が既知なら線形判別により簡単PSSM,Score,LinearInequality24NP-困難さの証明NP-hardifLisnotbounded(|Σ|=2)Reductionfrom3SAT3SAT:C={c1,c2,…,cn}overX={x1,…,xn}S(i,j,…):stringoflength4n

S[i]=1,S[j]=1,…?S[k]=0fortheotherpositionhNEG={S(),S(4n),S(i,j),S(i),S(2i-1,2i,4n)}POS={S(g(i1),4n)?S()?S(g(i2),4n)?S()?S(g(i3),4n)}forclausec=li1orli2orli3whereg(ik)=2ik-1ifli1ispositiveliteral,otherwiseg(ik)=2ikNP-困難さの証明NP-hardifLisnotb25位置依存スコア行列の-例からの推定について課件26Lを固定した場合の多項式時間アルゴリズムConstructanarrangementofhyperplanesin(|Σ|L+1)-dimensionalEuclideanspaceforthehyperplanes:Θ=f(S’)foreachsubstringS’oflengthLofeachsequenceinPOSUNEG

CheckeachcellinthearrangementApplicabletoderivationofhydropathicindicesbecausef1=f2=…=fL.Lを固定した場合の多項式時間アルゴリズムConstruct27ArrangementofHyperplanesCombinatorialandComputationalComexities:O(nd)fornplanesind-dimensionsThesignofy-fi(x)doesnotchangewithineachcellArrangementofHyperplanesComb28Lを固定した場合の補足Σ、Lを固定した場合、考慮すべき文字列の個數は定數個?多項式時間はtrivial位置に依存しないスコア行列（例えば、疎水性指標）の場合は、文字列の個數は定數個では無い（スコア行列のサイズはΣ）疎水性指標の學習：通常は膜貫通領域などのモチーフ領域が既知今回の結果はモチーフ領域が既知で無くても推定可能を示唆Lを固定した場合の補足Σ、Lを固定した場合、考慮すべき文字列29PSSMのMixtureの學習入力:POS,NEG,N(#PSSM)ただし全ての配列は同じ長さ出力:以下を満たすN個のPSSMの組(f1,…,fN)とΘPOS中の全ての配列Sについて、あるPSSMfk

が存在し、fk(S)>=ΘNEG中の全ての配列S,全てのPSSM

fk

について、fk(S)<ΘPSSMのMixtureの學習入力:PO