Computational investigation of protein functions is one of the most important task in the field of structural bioinformatics. In many cases, proteins exhibit their biological functions by interacting with other molecules so-called ligands, and thus ligand-binding sites can be regarded as functional units of the proteins. Interestingly, a common ligand-binding site can be conserved between different proteins whose sequences or folds are totally different. Therefore the comparison of protein-ligand binding sites, not protein global structures, is an appropriate approach to gaining functional and evolutionary knowledge about proteins. According to the progress of structural genomics projects, hundreds of thousands of protein-ligand binding interfaces are observed in Protein Data Bank (PDB). In addition to them, vast amounts of potential ligand-binding sites are also available by using various kinds of binding site prediction tools. Performing an exhaustive similarity search for such vast numbers of protein binding sites should provide the basis for automatic classification of protein functions. Moreover, such a systematic understanding of protein-ligand interactions can be exploited for structure-based drug design. However, the existing 3D alignment based methods can be applied only to a limited data set mainly due to the time complexity, and thus is not scalable to flood of structural data.

In this thesis, we present a fast and efficient method for enumerating similar pairs of binding sites, which is scalable to millions of binding sites. In the proposed method, binding sites are mapped onto feature space based on their geometrical and physicochemical properties first, and then similar pairs are enumerated by a fast neighbor search algorithm called SketchSort. A crucial point of our method is that the similar pairs in the feature space are detected by sorting operation that can be performed as approximately O(n), where n represents the number of binding sites. It is much faster than a brute-force pairwise comparison whose time complexity is O(n2) in case n is large. We showed that our method is over 100 times faster than FuzCav, a state-of-art binding sites similarity search method. We also evaluated the performance of our method from the viewpoint of accuracy. We performed two types of benchmark tests, in each of which the ability to recognize biologically related binding sites was measured using our method and FuzCav. In both tests, our results outperformed FuzCav in terms of sensitivity/specificity. We further conducted an additional test to check the ability for discriminating binding sites of the same ligand from the others. The result showed that our method is comparable or more accurate than an accurate 3D alignment program SiteEngine. These benchmarking results indicate that our method provides not only high-throughput, but also reliability for detecting biologically relevant binding sites in comparison to the existing methods.

Then, to demonstrate the performance and scalability with our method, We applied it to all-pair similarity searches for 1.8 million known and potential ligand-binding sites. The execution time to enumerate all similar pairs was within 4 days on a standard desktop machine (Intel Xeon 2.93 GHz). Consequently, we discovered over 11 million pairs of similar binding sites including several notable analogous sites, such as a similar nucleotide-binding site between different protein families or a similar calcium-binding site between distinct protein folds. It is the largest-scale study of binding site comparison for the PDB entries, as far as we know.

We further compiled the all detected pairs into a new database called Pocket Similarity Search using Multiple-sketches (PoSSuM), which is freely available for all researchers (http://possum.cbrc.jp/PoSSuM/). Since similar binding sites have already been enumerated and stored in our database, users can retrieve them rapidly, within a few seconds, through our web interface. Because all binding sites were annotated with information of various types such as CATH, SCOP, EC number and Gene Ontology, users can easily explore similar binding sites between proteins with different folds or similar catalytic sites between enzymes with different EC numbers. In comparison with an existing well known database, SitesBase, which includes approximately 33,000 known ligand-binding sites, our new database stores a much larger number of up-to-date known binding sites deposited in the PDB. In addition to them, our database includes pairs between known and potential ligand-binding regions predicted using a novel pocket detection program.

Our fast method and database are expected to be useful for annotation of protein functions and rapid screening of target proteins in drug design. In the near future, We are planning to extend our dataset to binding interfaces of proteins to proteins and to nucleic acids. Performing such a comprehensive search might engender identification of overlap regions of a protein and a small molecule; knowledge of such regions is expected to be useful for developing inhibitors for protein-protein interaction.

本論文は5章からなる。1章はイントロダクション、2章は類似したタンパク質とリガンドの結合部位を高速かつ正確に数え上げる計算方法を提案し、3章では提案手法を約120万箇所の結合部位へと適用し、4章では異なるタンパク質のファミリーへと適用し、5章では提案手法が予測したタンパク質リガンド結合部位のデータベースについて述べている。

1章では問題の背景について説明している。タンパク質とリガンドの結合部位を実験的に検証したデータは蓄積されているのもの、タンパク質およびリガンドの数が多いため、結合部位についての我々の知識は乏しい状態にある。そのため、既存の知識から結合部位を精度良く予測できる方法への期待は大きい。

2章では、予測を実現するための基礎的な情報として、タンパク質とリガンドの結合部位の3次元的構造情報から特徴量を抽出する方法を提案している。アプローチは、3次元構造を頂点間の辺から構成される三角形へとまず分解し、各三角形の辺の長さを5つのグループへと分類することで属性を取出し、さらに各頂点のアミノ酸残基の電荷チャージも属性として利用している。ここまでは既存の研究が採用している典型的アプローチであるが、従来の方法が属性の存在数により特徴量を記述していたのに対して、本研究では Gaussian kernel を使うことを提案している点があたらしい。結合部位の3次元的構造の類似性は、この特徴量ベクトルの正規化した内積として定義している点は従来手法を踏襲しているものの、Gaussian kernel による特徴量は従来の定義に比べて、類似構造の予測に威力を発揮することが ROC curve を使った分析から明らかになっている。

このように提案された新しい特徴量は予測に有効であることが明らかになった。しかしながら構造の類似性を比較する際にかかる計算時間は大きい。類似度の高い点の組を数え上げるステップが要となるが、対象とする点の数をn とするとき、すべての点間の類似度を計算する単純な網羅的な探索を実行すると n2 に比例する時間がかかるため、現実的な時間で計算することは困難になる。そこで3章では、田部井らによって開発されたランダムアルゴリズムに基づく計算方法を採用した場合の効果を検討している。このアルゴリズムを用いると、ある類似度以下の類似構造を若干のエラーが含まれるもののn に線形的に比例する時間で高速に計算できることを示している。エラー率の期待値を小さくできるようにパラメータをチューニングできるため、実用上は極めて低いエラー率で高速に類似構造を網羅できることが検証されている。

この高速手法を約120万箇所の結合部位へと適用し、4章では異なるタンパク質のファミリーへと適用している。これほど多くの結合部位の類似度を計算した前例研究はない。さらに5章では提案手法が予測したタンパク質リガンド結合部位のデータベースを公開している。このデータベースは、特定のタンパク質に結合することを想定して設計されたある化合物が、他のタンパク質に結合するかどうかを判定するのに使うことができるので、たとえば薬の副作用の可能性を検証するにはとても有用である。

以上のように提案方法は、正確性、高速性において従来手法を凌駕しており、公開されたデータベースは薬の安全性を評価する際に幅広く利用される可能性がある。なお、本論文は、田部井靖夫、清水佳奈、富井健太郎、津田宏治との共同研究であるが、論文提出者が主体となって開発、分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。