Algorithmic and Artificial Intelligence Methods for Protein Bioinformatics

Chapter 21

Efficient Alignments of Metabolic Networks with Bounded Treewidth

QIONG CHENG, PIOTR BERMAN, ROBERT W. HARRISON and ALEXANDER ZELIKOVSKY

21.1 Introduction

The accumulation of results of thousands of experiments, as well as high-throughput genomic, proteomic, and metabolic data, allows for increasingly accurate modeling and reconstruction of biological molecular interactions in the form of metabolic, regulatory, and signal transduction networks that are critical to understanding of vital cellular processes. With the growth of identified biological networks stored in several public collections of databases (e.g., KEGG [17] and BioCyc [6]), the development of efficient computational tools for assessing, comparing, and curating the wealth of data has become essential.

Many such needs can be addressed by a network alignment approach that can be used for comparing biological networks between different species to reveal evolutionary conservation of most vital life processes. We investigate a general network alignment problem—a pathway forms a pattern, and a cellular network (usually from another species) forms the text, and we want to find the best correspondence between the text and the pattern. Existing approaches suffer from low scalability even when applied to usually sparse graphs.

The authors in this chapter develop a computationally much more efficient approach based on homomorphisms and homeomorphisms, allowing toleration of the divergence within the alignment of metabolic ...