Repository: Freie Universit├Ąt Berlin, Math Department

k-PathA: k-shortest Path Algorithm

Ullrich, Alexander and Forst, Christian V. (2009) k-PathA: k-shortest Path Algorithm. In: High Performance Computational Systems Biology (HiBi 2009), September 2009, Trento, Italy.

[img] PDF - Published Version
Restricted to Registered users only



One important aspect of computational systems biology includes the identification and analysis of functional response networks within large biochemical networks. These functional response networks represent the response of a biological system under a particular experimental condition which can be used to pinpoint critical biological processes. For this purpose, we have developed a novel algorithm to calculate response networks as scored/weighted sub-graphs spanned by k-shortest simple (loop free) paths. The k-shortest simple path algorithm is based on a forward/backward chaining approach synchronized between pairs of processors. The algorithm scales linear with the number of processors used. The algorithm implementation is using a Linux cluster platform, MPI lam and mpiJava messaging as well as the Java language for the application. The algorithm is performed on a hybrid human network consisting of 45,041 nodes and 438,567 interactions together with gene expression information obtained from human cell-lines infected by influenza virus. Its response networks show the early innate immune response and virus triggered processes within human epithelial cells. Especially under the imminent threat of a pandemic caused by novel influenza strains, such as the current H1N1 strain, these analyses are crucial for a comprehensive understanding of molecular processes during early phases of infection. Such a systems level understanding may aid in the identification of therapeutic markers and in drug development for diagnosis and finally prevention of a potentially dangerous disease.

Item Type:Conference or Workshop Item (Paper)
Subjects:Biological Sciences
Mathematical and Computer Sciences
ID Code:1118
Deposited By: BioComp Admin
Deposited On:26 Jan 2012 10:39
Last Modified:03 Mar 2017 14:41

Repository Staff Only: item control page