Finding Pathway Structures in Protein Interaction Networks |
| |
Authors: | Songjian Lu Fenghui Zhang Jianer Chen Sing-Hoi Sze |
| |
Affiliation: | (1) Department of Computer Science, Texas A&M University, College Station, TX 77843, USA;(2) Department of Biochemistry & Biophysics, Texas A&M University, College Station, TX 77843, USA |
| |
Abstract: | The increased availability of data describing biological interactions provides important clues on how complex chains of genes
and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures
such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures
are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find
an optimal path structure in
time and
space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number
of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure.
Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity
is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures,
we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures
with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity
by applying it to protein interaction networks in the DIP database. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|