Title: Improving the accuracy of signal transduction pathway construction using level-2 neighbours

Authors: Thomas K.F. Wong, T.W. Lam, S.M. Yiu, Simon C.K. Wong

Addresses: Faculty of Engineering, Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong. ' Faculty of Engineering, Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong. ' Faculty of Engineering, Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong. ' Faculty of Engineering, Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong

Abstract: In this paper, we consider the problem of reconstructing a pathway for a given set of proteins based on available genomics and proteomics information such as gene expression data. In all previous approaches, the scoring function for a candidate pathway usually only depends on adjacent proteins in the pathway. We propose to also consider proteins that are of distance two in the pathway (we call them Level-2 neighbours). We derive a scoring function based on both adjacent proteins and Level-2 neighbours in the pathway and show that our scoring function can increase the accuracy of the predicted pathways through a set of experiments. The problem of computing the pathway with optimal score, in general, is NP-hard. We thus extend a randomised algorithm to make it work on our scoring function to compute the optimal pathway with high probability.

Keywords: protein pathway construction; signal transduction pathways; level-2 neighbours; system biology; protein pathways; pathway construction; MAPK pathway construction; randomised algorithms; cell cycle pathway construction; gene expression; bioinformatics.

DOI: 10.1504/IJBRA.2010.038736

International Journal of Bioinformatics Research and Applications, 2010 Vol.6 No.6, pp.542 - 555

Received: 17 Jan 2008
Accepted: 20 Aug 2008

Published online: 24 Feb 2011 *

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