Mapping of orthologous genes in the context of biological pathways: An application of integer programming

Abstract

Mapping biological pathways across microbial genomes is a highly important technique in functional studies of biological systems. Existing methods mainly rely on sequence-based orthologous gene mapping, which often leads to suboptimal mapping results because sequence-similarity information alone does not contain sufficient information for accurate identification of orthology relationship. Here we present an algorithm for pathway mapping across microbial genomes. The algorithm takes into account both sequence similarity and genomic structure information such as operons and regulons. One basic premise of our approach is that a microbial pathway could generally be decomposed into a few operons or regulons. We formulated the pathway-mapping problem to map genes across genomes to maximize their sequence similarity under the constraint that the mapped genes be grouped into a few operons, preferably coregulated in the target genome. We have developed an integer-programming algorithm for solving this constrained optimization problem and implemented the algorithm as a computer software program, p-map. We have tested p-map on a number of known homologous pathways. We conclude that using genomic structure information as constraints could greatly improve the pathway-mapping accuracy over methods that use sequence-similarity information alone.

Fig. 1.

IP formulation for the pathway-mapping problem. Circles represent genes in the template pathway; rectangles represent candidate genes in the target genome, where target candidate genes are obtained through blast search with a specific e-value cutoff; cylinders represent operons; and cubes represent regulons. A line between a template gene and target candidate gene represents a blast hit. A line between a target candidate gene and an operon indicates that the gene belongs to this operon, and a line between an operon and a regulon indicates that the operon belongs to the regulon.