Title: Protein complex prediction via improved verification methods using constrained domain-domain matching

Authors: Yang Zhao; Morihiro Hayashida; Jose C. Nacher; Hiroshi Nagamochi; Tatsuya Akutsu

Addresses: Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, 611-0011, Japan ' Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, 611-0011, Japan ' Department of Complex and Intelligent Systems, Future University-Hakodate, 116-Kamedankano, Hakodate, Hokkaido 041-8655, Japan ' Graduate School of Informatics, Department of Applied Mathematics and Physics, Kyoto University, Yoshida Honmachi, Sakyo, Kyoto, 606-8501, Japan ' Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, 611-0011, Japan

Abstract: Identification of protein complexes within protein-protein interaction networks is one of the important objectives in functional genomics. Ozawa et al. proposed a verification method of protein complexes by introducing a structural constraint. In this paper, we propose an improved integer programming-based method based on the idea that a candidate complex should not be divided into many small complexes, and combination methods with maximal components and extreme sets. The results of computational experiments suggest that our methods outperform the method by Ozawa et al. We prove that the verification problems are NP-hard, which justifies the use of integer programming.

Keywords: protein complex prediction; integer programming; DDI; domain-domain interactions; PPI; protein-protein interactions; bioinformatics; protein complexes; constrained domain-domain matching; verification methods.

DOI: 10.1504/IJBRA.2012.048970

International Journal of Bioinformatics Research and Applications, 2012 Vol.8 No.3/4, pp.210 - 227

Published online: 05 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article