The availability of large scale protein interaction networks for several species has motivated many comparative studies in recent years. These studies typically employ network alignment algorithms for the task and use the sequence similarity of proteins to aid the alignment process. In this thesis I use a quantitative measure of protein functional similarity and show that the results are superior to sequence based network alignment. I present a method for module detection that combines results from network alignments with clustering measures to achieve superior results over several existing methods. Next, I address the issue of generally low conservation detected by alignments of interaction networks from model organisms. By explicitly modelling evolutionary mechanisms on pairs of networks I test the hypothesis that divergent evolution alone may be the cause. I use a distance metric based on graph summary statistics to assess the fit between experimental and simulated network alignments. Our results indicate that network evolution alone is unlikely to account for the poor quality alignments given by real data. We also find that false positives appear to affect network alignments little compared to false negatives indicating that incompleteness, not spurious links, is the major challenge for interactome-level comparisons. Finally, I focus on the comparative analysis of a subset of the interaction network related to mitosis in Yeast, Human and Fly. Manual ordering of mitosis-related functional annotations allows the study of temporal aspects of the network. I also use a Markov random field approach to infer temporal labels for unlabelled proteins. Sequence based network alignment of the mitotic networks in the three species finds little conservation despite the proteins being functionally very similar. Further investigation suggests a fuzzy relationship between protein sequence and function that may have implications for future network alignment studies.

The accumulation of high-throughput genomic and proteomic data allows for the reconstruction of the increasingly large and complex metabolic networks. In order to analyze the accumulated data and reconstructed networks, it is critical to identify network patterns and evolutionary relations between metabolic networks. But even finding similar networks becomes computationally challenging. The dissertation addresses these challenges with discrete optimization and the corresponding algorithmic techniques. Based on the property of the gene duplication and function sharing in biological network,we have formulated the network alignment problem which asks the optimal vertex-to-vertex mapping allowing path contraction, vertex deletion, and vertex insertions. We have proposed the first polynomial time algorithm for aligning an acyclic metabolic pattern pathway with an arbitrary metabolic network. We also have proposed a polynomial-time algorithm for patterns with small treewidth and implemented it for series-parallel patterns which are commonly found among metabolic networks. We have developed the metabolic network alignment tool for free public use. We have performed pairwise mapping of all pathways among five organisms and found a set of statistically significant pathway similarities. We also have applied the network alignment to identifying inconsistency, inferring missing enzymes, and finding potential candidates.

Comparative analysis of genomic data investigates the relationship of genome structure and function across different biological species to shed light on their similarities and differences. In this dissertation, we study two important problems in comparative genomics, namely comparative sequence analysis and comparative network analysis. In the comparative sequence analysis, we study the multiple sequence alignment of protein and DNA sequences as well as the structural alignment of multiple RNA sequences. For closely related sequences, multiple sequence alignment can be efficiently performed through progressive techniques. However, for divergent sequences it is very challenging to predict an accurate alignment. Here, we introduce PicXAA, an efficient non-progressive technique for multiple protein and DNA sequence alignment. We also further extend PicXAA to PicXAA-R for structural alignment of RNA sequences. PicXAA and PicXAA-R greedily build up the alignment from sequence regions with high local similarity, thereby yielding an accurate global alignment that effectively captures local similarities among sequences. As another important research area in comparative genomics, we also investigate the comparative network analysis problem. Translation of increasing number of large-scale biological networks into meaningful biological insights requires efficient computational techniques. One such example is network querying, which aims to identify subnetwork regions in a large target network that are similar to a given query network. Here, we introduce an efficient algorithm for querying large-scale biological networks, called RESQUE. RESQUE adopts a semi-Markov random walk model to probabilistically estimate the correspondence scores between nodes that belong to different networks. The target network is iteratively reduced based on the estimated correspondence scores until the best matching subnetwork emerges. The proposed network querying scheme is computationally efficient, can handle any network query with an arbitrary topology, and yields accurate querying results. We also extend the idea used in RESQUE to develop an efficient algorithm for alignment of multiple large-scale biological networks, called SMETANA. SMETANA outperforms state-of- the-art network alignment techniques, in terms of both computational efficiency and alignment accuracy. The accomplished studies have enabled us to provide a coherent framework for probabilistic approach to comparative analysis of biological sequences and networks. Such a probabilistic framework helps us employ rigorous mathematical schemes to find accurate and efficient solutions to these problems.

Much research has been directed toward understanding the roles of essential components in the cell, such as proteins, microRNAs, and genes. This dissertation focuses on two interesting problems in bioinformatics research: microRNA-target prediction and the identification of conserved protein complexes across species. We define the two problems and develop novel approaches for solving them. MicroRNAs are short non-coding RNAs that mediate gene expression. The goal is to predict microRNA targets. Existing methods rely on sequence features to predict targets. These features are neither sufficient nor necessary to identify functional target sites and ignore the cellular conditions in which microRNA and mRNA interact. We developed MicroTarget to predict microRNA-mRNA interactions using heterogeneous data sources. MicroTarget uses expression data to learn candidate target set for each microRNA. Then, sequence data is used to provide evidence of direct interactions and ranking the predicted targets. The predicted targets overlap with many of the experimentally validated ones. The results indicate that using expression data helps in predicting microRNA targets accurately. Protein complexes conserved across species specify processes that are core to cell machinery. Methods that have been devised to identify conserved complexes are severely limited by noise in PPI data. Behind PPIs, there are domains interacting physically to perform the necessary functions. Therefore, employing domains and domain interactions gives a better view of the protein interactions and functions. We developed novel strategy for local network alignment, DONA. DONA maps proteins into their domains and uses DDIs to improve the network alignment. We developed novel strategy for constructing an alignment graph and then uses this graph to discover the conserved sub-networks. DONA shows better performance in terms of the overlap with known protein complexes with higher precision and recall rates than existing methods. The result shows better semantic similarity computed with respect to both the biological process and the molecular function of the aligned sub-networks. / Ph. D.

No description available.

Network alignment is the problem of finding a common subgraph between two graphs, and more generally <i>k </i>graphs. The results of network alignment are often used for information transfer, which makes it a powerful tool for deducing information or insight about networks. Network alignment is tightly related to the subgraph isomorphism problem which is known to be NP-hard, this makes the network alignment problem supremely hard in practice. Some algorithms have been devised to approach it via solving a form of a relaxed version of the NP-hard problem or by defining certain heuristic measures. These algorithms normally work well for problems when there is some form of prior known similarity between the nodes of the graphs to be aligned. The absence of such information makes the problem more challenging. In this scenario, these algorithms would often require much more time to finish executing, and even fail sometimes. The version of network alignment that this thesis tackles is the one when such prior similarity measures are absent. In this thesis, we address three versions of network alignment: (i) multimoal network alignment, (ii) standard pairwise network alignment, and (iii) multiple network alignment. A key common component of the algorithms presented in this thesis is exploiting a low rank structure in the network alignment problem and thus producing algorithms that run much faster than classic network alignment algorithms.

Multiple users compete for a common resource like bandwidth to communicate data in interference networks. Existing approaches in dealing with interference limit the rate of communication due to paucity of shared resources. This limitation in the rate gets more glaring as the number of users in the network increases. For example, existing wireless systems either choose to orthogonalize the users (for example, Frequency Division Multiple Access (FDMA) systems or Code Division Multiple Access (CDMA) systems) or treat interference as Gaussian noise at the receivers. It is well known that these approaches are sub-optimal in general. Orthogonalization of users limit the number of available interference-free channels (known as degrees of freedom, abbreviated as DoF) and treating interference as noise means that the receiver cannot make use of the structure in the interfering signals. This motivates the need to analyze alternate transmit and decoding schemes in interference networks. This thesis mainly analyzes transmit schemes that use linear precoding for various configurations of interference networks with some practical constraints imposed by the use of finite input constellations, propagation delays, and channel state availability at the transmitters. The main contributions of this thesis are listed below. Achievable rates using precoding with finite constellation inputs in Gaussian Interference Channels (GIC) is analyzed. A metric for finding the approximate angle of rotation to maximally enlarge the Constellation Constrained (CC) capacity of two-user Gaussian Strong Interference Channel (GSIC) is proposed. Even as the Gaussian alphabet FDMA rate curve touches the capacity curve of the GSIC, with both the users using the same finite constellation, we show that the CC FDMA rate curve lies strictly inside the CC capacity curve at high powers. For a K-user MIMO GIC, a set of necessary and sufficient conditions on the precoders under which the mutual information between between relevant transmit-receive pairs saturate like in the single user case is derived. Gradient-ascent based algorithms to optimize the sum-rate achieved by precoding with finite constellation inputs and treating interference as noise are proposed. For a class of Gaussian interference networks with general message demands, identified as symmetrically connected interference networks, the expected sumspectral efficiency (in bits/sec/Hz) is shown to grow linearly with the number of transmitters at finite SNR, using a time-domain Interference Alignment (IA) scheme in the presence of line of sight (LOS) channels. For a 2×2 MIMO X-Network with M antennas at each node, we identify spacetime block codes that could be coupled with an appropriate precoding scheme to achieve the maximum possible sum-DoF of 4M 3 , for M = 3, 4. The proposed schemes are shown to achieve a diversity gain of M with SNR-independent finite constellation inputs. The proposed schemes have lower CSIT requirements compared to existing schemes. This thesis also makes an attempt to guarantee a minimum throughput when the zero-interference conditions cannot be satisfied in a wireline network with three unicast sessions with delays, using Precoding Based Network Alignment (PBNA). Three different PBNA schemes namely PBNA with time-varying local encoding coefficients (LECs), PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs are proposed and their feasibility conditions analyzed.