SGER: NET HMMs and Their Applications to Biological Network Alignment

William Marsh Rice University, Houston TX

Investigators

Abstract

Biological interaction networks are graphs in which nodes represent molecules, such as genes or proteins, and edges represent interactions among the molecules. These networks underly and govern the mechanisms of cellular decision-making, and play major roles in understanding causes of different diseases, as well as designing effective, targeted therapeutics. Advances in biotechnologies are amassing large amounts of these types of data from multiple organisms. One powerful tool for analyzing such data and elucidating functional components in them is through comparative analysis by means of network alignment. Roughly speaking, aligning a pair of networks, typically from two different organisms, entail finding the ?evolutionary correspondence? between the nodes of the networks. This pairwise alignment is also generalizable to multiple networks. The rationale behind aligning a set of networks is identifying subsets of these networks that are conserved across organisms, which are natural candidates for functional molecular components. This research will develop models and algorithms for aligning interaction networks and identifying conserved elements via a probabilistic framework that uses hidden Markov models (HMMs). Despite the success of HMMs in a variety of biological applications, mainly in the sequence analysis area, they have not been considered in the realm of network alignment. The reason for this has been that while HMMs naturally apply to one-dimensional data, such as sequences or columns of a matrix, they do not apply to multidimensional data, such as graphs. To achieve this goal, the investigator will conduct research in two areas. First, the investigator will formulate an HMM-based framework for alignment multiple biological interaction networks. This part entails devising strategies for identifying a mapping among nodes of the networks and devising schemes for handling matches, mismatches, insertions, and deletions in these networks. Second, the investigator will design novel algorithms that enable the HMM to ?operate? in a multi-dimensional space.