Network Alignments

Metabolism is a vital cellular process whose understanding is critical to human disease studies and drug discovery. The accumulation of high-throughput genomic, proteomic and metabolical data allows for increasingly accurate modeling and reconstruction of metabolic networks. Alignment of the reconstructed networks can catch model inconsistencies and infer missing elements. Existing alignment tools are mostly based on isomorphic and homeomorphic embedding effectively solving a problem that is NP-complete even when searching a match for a tree in acyclic networks.

In this project, we

- Designed the first polynomial-time algorithm for efficiently finding optimal homo-homeomorphic embedding from multi-source trees into arbitrary networks which allow for enzyme deletions and insertions.

- Extended the algorithm to arbitrary networks even with cycles.

- Proposed a framework of detecting and filling pathways by embedding sequence alignment tools and doing a database search for missing enzymes and proteins with the matching prosites and the resulting high sequence similarity.

- Implemented a web service tool MetNetAligner which can be used for predicting unknown pathways, comparing and finding conserved patterns, and resolving ambiguous identification of enzymes. The tool supports two alignment algorithms.

Team members

Qiong Cheng Dr. Alexander Zelikovsky

Collaborators

Dr. Robert Harrison

Dr. Piotr Berman

- Published papers: Recomb Satellite'07 paper, BIBE'07 paper , BIBE'07 slides , ISBRA'07 , CSBS 2007

-- Tool Website

Software architecture:

Configuration interface:

A sample of the mapping result: