タンパク質間相互作用強度予測の高速化と困難性

摘要

タンパク質間相互作用は遺伝子発現，シグナル伝達などの生体内のプロセスにおいて重要な役割を果たすため，計算機による様々な予測手法が提案されてきた．その中でよく研究されている手法に．ドメイン間相互作用に基づいた予測法がある．この手法を応用し相互作用の強度についてもLPNM法と呼ばれる手法が提案されたが，線形計画法に基づいているため大きなデータに対しては大きな計算時間がかかる．本論文では，より高速なタンパク質間相互作用強度予測手法を提案する．実際にyeast two-hybridの生物実験データに適用し，LPNM法に比して計算時間で150分の1以下，予測性能では同程度の精度を達成した．これらの手法を開発する上で，問題の困難さを計算量の立場から考察することは欠かせない．そのため，まずタンパク質間相互作用について，予測精度を最大化する問題はMAX SNP困難であることを証明した．これは同時にNP困難であるとともに，P≠NPの仮定のもとで，任意の近似比で近似する多項式時間アルゴリズムは存在しないことを意味する．