位置依存スコア行列の-例からの推定について课件

1、位置依存行列例推定阿久津達也takutsukuicr.kyoto-u.ac.jp京都大学化学研究所位置依存行列例推定阿久津達也位置依存行列位置依存行列関数推定問題定義入力正例: X1,X2,X3,負例: Y1,Y2,Y3,出力：以下満 関数X1,X2,X3, 最適 (、値以上)Y1,Y2,Y3, 非最適(値以下)関数推定問題定義入力関数推定関理論的結果最適化/同定関数学習PP (ICALP98)HardHard (ICALP98)RNA二次構造予測PP (ICALP98)質HardHard (ICALP98)疎水性指標PP (new)位置依存行列PHard (new)混合分布PHard (ne

2、w)関数推定関理論的結果最適化/関数学習位置依存行列推定入力:POS (上文字列集合、正例)NEG (上文字列集合、負例)L (領域長)出力: PSSM f 値 s.t.For all S in POS, there is a substring S of S for which f(S) = For all S in NEG, for all substring S of S, f(S) = X1,T+X2,G+X3,C = 領域既知線形判別簡単PSSM, Score, Linear InequalityNP-困難証明NP-hard if L is not bounded (|=2)Redu

3、ction from 3SAT3SAT: C = c1,c2,cn over X = x1,xn S (i,j,) : string of length 4n Si=1,Sj=1, Sk=0 for the other position hNEG =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) for clause c=li1 or li2 or li3 where g(ik)=2ik-1 if li1 is positive literal, otherwise g(ik)=2

4、ikNP-困難証明NP-hard if L is not b位置依存行列-例推定课件L固定場合多項式時間Construct an arrangement of hyperplanes in (|L+1)-dimensional Euclidean space for the hyperplanes:= f(S) for each substring S of length L of each sequence in POS U NEG Check each cell in the arrangementApplicable to derivation of hydropathic indice

5、s because f1=f2=fL.L固定場合多項式時間Construct Arrangement of HyperplanesCombinatorial and Computational Comexities: O(nd ) for n planes in d-dimensionsThe sign of y-fi (x) does not change within each cellArrangement of HyperplanesCombL固定場合補足、L固定場合、考慮文字列個数定数個多項式時間trivial位置依存行列（例、疎水性指標）場合、文字列個数定数個無（行列）疎水性指標学習：通常膜貫通領域領域既知今回結果領域既知無推定可能示唆L固定場合補足、L固定場合、考慮文字列PSSMMixture学習入力: POS, NEG, N (#PSSM) 全配列同長出力: 以下満N個PSSM組 (f 1, , f N) POS中全配列S、PSSM f k 存在、f k(S )= NEG中全配列S, 全PSSM f k 、f k(S ) = for each S in POSf(S)= 、score(Yi,Yi) 既存手法頻度基(PAM、BLOSUM)最適化基手法(Goldstein, 蓬来)問題点：必要結果文字数（残基数）制約無場合