Andreas Wagner

Paper #: 01-09-050

I present an algorithm that determines the longest path between every gene pair in an arbitrarily large genetic network from large-scale gene perturbation data. As a by-product, the algorithm reconstructs all direct regulatory gene interactions in the network. The algorithm is recursive, and is built around a graph representation of genetic networks. Its computational complexity is $O(nk2)$, where $n$ is the number of genes in the network, and $k$ is the average number of genes affected by a genetic perturbation. In practice, it can reconstruct all path lengths for a network of more than 6000 genes in less than 30 CPU seconds. It is able to distinguish a large fraction of direct regulatory interactions from indirect interactions, even if the quality of its input data is substantially compromised.