Abstract
With the large availability of protein-protein interaction data, to identify linear biological meaningful pathways in the sense of optimality on likelihood weights is regarded as a NP-problem. We proposed a color-coding method based on the characteristics of biological network topology to solve this problem and applied an A* heuristic search to speed up the color-coding method in order to extract minimum weight of pathways that most likely have protein-protein interactions corresponding to the microarray data. In the experiments, we tested the methods by applying them to the networks of yeast and human prostate cancer and the results showed that we were able to reconstruct known signaling pathways in comparison to the recent KEGG pathway database. Our algorithms are more efficient than the previous ones and can detect optimal and functional enrichment paths of length 8 within 6 seconds and paths of length 10 within 29 seconds on average.