Finding Pathway Structures in Protein Interaction Networks

@article{citeulike:1558218, abstract = {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.}, author = {Lu, Songjian and Zhang, Fenghui and Chen, Jianer and Sze, Sing-Hoi }, citeulike-article-id = {1558218}, doi = {10.1007/s00453-007-0155-7}, journal = {Algorithmica}, keywords = {algorithms, biology, complex}, number = {4}, pages = {363--374}, posted-at = {2007-08-13 17:12:35}, priority = {5}, title = {Finding Pathway Structures in Protein Interaction Networks}, url = {http://dx.doi.org/10.1007/s00453-007-0155-7}, volume = {48}, year = {2007} }

TY - JOUR ID - citeulike:1558218 L3 - citeulike-article-id:1558218 TI - Finding Pathway Structures in Protein Interaction Networks JF - Algorithmica VL - 48 IS - 4 SP - 363 EP - 374 N2 - 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. KW - algorithms KW - biology KW - complex AU - Lu, Songjian AU - Zhang, Fenghui AU - Chen, Jianer AU - Sze, Sing-Hoi PY - 2007//25/ UR - http://dx.doi.org/10.1007/s00453-007-0155-7 ER -