Search

Dynamic biological networks model changes in the network topology over time. However, often the topologies of these networks are not available at specific time points. Existing algorithms for studying dynamic networks often ignore this problem and focus only on the time points at which experimental data is available. In this paper, we develop a novel alignment based network construction algorithm, ANCA , that constructs the dynamic networks at the missing time points by exploiting the information from a reference dynamic network. Our experiments on synthetic and real networks demonstrate that ANCA predicts the missing target networks accurately, and scales to large-scale biological networks in practical time. Our analysis of an E. coli protein-protein interaction network shows that ANCA successfully identifies key temporal changes in the biological networks. Our analysis also suggests that by focusing on the topological differences in the network, our method can be used to find important genes and temporal functional changes in the biological networks.

In bioinformatics, complex cellular modeling and behavior simulation to identify significant molecular interactions is considered a relevant problem. Traditional methods model such complex systems using single and binary network. However, this model is inadequate to represent biological networks as different sets of interactions can simultaneously take place for different interaction constraints (such as transcription regulation and protein interaction). Furthermore, biological systems may exhibit varying interaction topologies even for the same interaction type under different developmental stages or stress conditions. Therefore, models which consider biological systems as solitary interactions are inaccurate as they fail to capture the complex behavior of cellular interactions within organisms. Identification and counting of recurrent motifs within a network is one of the fundamental problems in biological network analysis. Existing methods for motif counting on single network topologies are inadequate to capture patterns of molecular interactions that have significant changes in biological expression when identified across different organisms that are similar, or even time-varying networks within the same organism. That is, they fail to identify recurrent interactions as they consider a single snapshot of a network among a set of multiple networks. Therefore, we need methods geared towards studying multiple network topologies and the pattern conservation among them. Contributions: In this paper, we consider the problem of counting the number of instances of a user supplied motif topology in a given multilayer network. We model interactions among a set of entities (e.g., genes)describing various conditions or temporal variation as multilayer networks. Thus a separate network as each layer shows the connectivity of the nodes under a unique network state. Existing motif counting and identification methods are limited to single network topologies, and thus cannot be directly applied on multilayer networks. We apply our model and algorithm to study frequent patterns in cellular networks that are common in varying cellular states under different stress conditions, where the cellular network topology under each stress condition describes a unique network layer.We develop a methodology and corresponding algorithm based on the proposed model for motif counting in multilayer networks. We performed experiments on both real and synthetic datasets. We modeled the synthetic datasets under a wide spectrum of parameters, such as network size, density, motif frequency. Results on synthetic datasets demonstrate that our algorithm finds motif embeddings with very high accuracy compared to existing state-of-the-art methods such as G-tries, ESU (FANMODE)and mfinder. Furthermore, we observe that our method runs from several times to several orders of magnitude faster than existing methods. For experiments on real dataset, we consider Escherichia coli (E. coli)transcription regulatory network under different experimental conditions. We observe that the genes selected by our method conserves functional characteristics under various stress conditions with very low false discovery rates. Moreover, the method is scalable to real networks in terms of both network size and number of layers.

Cells, in order to regulate their activities, process transcripts by controlling which genes to transcribe and by what amount. The transcription level of genes often change over time. Rate of change of gene transcription varies between genes. It can even change for the same gene across different members of a population. Thus, for a given gene, it is important to study the transcription level not only at a single time point, but across multiple time points to capture changes in patterns of gene expression which underlies several phenotypic or exiernal factors. In such a dataset perturbation can happen due to which it may have missing transcription values for different samples at different time points. In this paper, we define three data perturbation models that are significant with respect to random deletion. We also define a recovery method that recovers data loss in the perturbed dataset such that the error is minimized. Our experimental results show that the recovery method compensates for the loss made by perturbation models. We show by means of two measures, namely, normalized distance and Pearson's correlation coefficient that the distance between the original and perturbed dataset is more than the distance between original and recovered dataset.

Biological networks provide great potential to understand how cells function. Motifs in biological networks, frequent topological patterns, represent key structures through which biological networks operate. Studying motifs answers important biological questions. Finding motifs in biological networks remains to be a computationally challenging task as the sizes of the motif and the underlying network grow. Several algorithms exist in the literature to solve this problem. This chapter discusses the biological significance of network motifs, motivation behind solving the motif detection problem and the key challenges of this problem. We discuss different formulations of motif detection problem based on several orthogonal perspectives that change the problem definition as well as solution significantly. The first perspective considers the number of input networks involved (i.e., one or more than one networks). The second perspective focuses on the labeling (i.e., labeled or unlabeled) of the nodes and edges of the input network. The third one considers different frequency definitions of counting motif instances (i.e., F1, F2, and F3) in a network. The fourth perspective describes whether the underlying network is directed or undirected. The last one considers motif detection under different types of network models (i.e., deterministic, probabilistic, or dynamic model). As a case study for each formulation, we briefly discuss important existing methods from the literature. Finally, we conclude with future research directions.

Protein-protein interaction (PPI) network models interconnections between protein-encoding genes. A group of proteins that perform similar functions are often connected to each other in the PPI network. The corresponding genes form pathways or functional modules. Mutation in protein-encoding genes affect behavior of pathways. This results in initiation, progression, and severity of diseases that propagates through pathways. In this work, we integrate mutation, survival information of patients, and PPI network to identify connected subnetworks associated with survival. We define the computational problem using a fitness function called log-rank statistic to score subnetworks. Log-rank statistic compares the survival between two populations. We propose a novel method, Survival Associated Mutated Subnetwork (SAMS) that adopts genetic algorithm strategy to find the connected subnetwork within the PPI network whose mutation yields highest log-rank statistic. We test on real cancer and synthetic datasets. SAMS generate solutions in negligible time while the state-of-art method in literature takes exponential time. Log-rank statistic of SAMS selected mutated subnetworks are comparable to the method. Our result genesets show significant overlap with well-known cancer driver genes derived from curated datasets and studies in literature, display high text-mining score in terms of number of citations combined with disease-specific keywords in PubMed, and identify pathways having high biological relevance.

Motivation: Traditional methods often represent complex systems as a single, static, and binary network. These models are inadequate in capturing complex cellular interactions which vary under different conditions as well as over time. Furthermore the same set of molecules can interact in varying patterns across different interactomes. In this paper, we model cellular interactions as a set of network topologies, called multilayer networks. We consider motif counting, one of the most fundamental problems in network analysis. Existing motif counting and identification methods are limited to single network topologies, and thus they cannot be directly applied on multilayer networks. Results: In this paper, we extend the classical network motif identification problem to multilayer networks. We develop an efficient and accurate method to solve this problem. Our results on Escherichia coli (E.coli) transcription regulatory network under different experimental conditions show that our method scales to real networks and more importantly can uncover conserved functional characteristics of genes participating in the network under various conditions with very low false discovery rates.

Biological networks describe the interactions among molecules. Unlike static biological networks at a single time point, temporal networks capture how the network topology evolves over time in response to external stimuli or internal variations. We say that two temporal networks have co-evolving subnetworks if the topologies of these subnetworks remain similar to each other as the networks evolve over time. Existing methods for identifying co-evolving patterns make the strong and unrealistic assumption that the two network topologies evolve at the same rate. In this paper, we consider the generalized problem, where each network may evolve at different rates and the rates of evolution may change over time. Moreover, the two networks may have network topologies available for different number of time points. Existing methods fail to solve this problem as they rely on the strong prior assumption. We develop an efficient algorithm, Tempo++, for identifying co-evolving subnetworks within two given temporal networks. Unlike existing methods, Tempo++ does not assume that the networks have same and uniform evolutionary rates. We experimentally demonstrate that Tempo++ scales efficiently and accurately on both synthetic and real datasets. Our results on E. coli time resolved response to five different environmental stress conditions demonstrate that Tempo++ identifies genes specific to those conditions that conforms to well-known studies in the literature. Statistical significance of alignments found by Tempo++ outperforms existing strategies. Moreover, Tempo++ correctly identifies co-evolving networks with similar stress response compared to networks with different stress response.

Biological networks provide great potential to understand how cells function. Motifs are topological patterns which are repeated frequently in a specific network. Network motifs are key structures through which biological networks operate. However, counting independent (i.e., non-overlapping) instances of a specific motif remains to be a computationally hard problem. Motif counting problem becomes computationally even harder for biological networks as biological interactions are uncertain events. The main challenge behind this problem is that different embeddings of a given motif in a network can share edges. Such edges can create complex computational dependencies between different instances of the given motif when considering uncertainty of those edges. In this paper, we develop a novel algorithm for counting independent instances of a specific motif topology in probabilistic biological networks. We present a novel mathematical model to capture the dependency between each embedding and all the other embeddings, which it overlaps with. We prove the correctness of this model. We evaluate our model on real and synthetic networks with different probability, and topology models as well as reasonable range of network sizes. Our results demonstrate that our method counts non-overlapping embeddings in practical time for a broad range of networks.

MotivationBiological networks describes the mechanisms which govern cellular functions. Temporal networks show how these networks evolve over time. Studying the temporal progression of network topologies is of utmost importance since it uncovers how a network evolves and how it resists to external stimuli and internal variations. Two temporal networks have co-evolving subnetworks if the topologies of these subnetworks remain similar to each other as the network topology evolves over a period of time. In this paper, we consider the problem of identifying co-evolving pair of temporal networks, which aim to capture the evolution of molecules and their interactions over time. Although this problem shares some characteristics of the well-known network alignment problems, it differs from existing network alignment formulations as it seeks a mapping of the two network topologies that is invariant to temporal evolution of the given networks. This is a computationally challenging problem as it requires capturing not only similar topologies between two networks but also their similar evolution patterns.ResultsWe present an efficient algorithm,Tempo, for solving identifying coevolving subnetworks with two given temporal networks. We formally prove the correctness of our method. We experimentally demonstrate that Tempo scales efficiently with the size of network as well as the number of time points, and generates statistically significant alignments—even when evolution rates of given networks are high. Our results on a human aging dataset demonstrate that Tempo identifies novel genes contributing to the progression of Alzheimer’s, Huntington’s and Type II diabetes, while existing methods fail to do so.AvailabilitySoftware is available online (https://www.cise.ufi.edu/∼relhesha/temporal.zip).Contactrelhesha@ufi.eduSupplementary informationSupplementary data are available atBioinformaticsonline.

Biological networks provide great potential to understand how cells function. Network motifs, frequent topological patterns, are key structures through which biological networks operate. Counting independent (i.e. non-overlapping) copies of a given motif however remains to be a computationally hard problem. Motif counting problem becomes computationally even harder for biological networks as biological interactions are uncertain events. The central challenge behind this problem is that different embeddings of a given motif in a network can share edges. Such edges can create complex computational dependencies between different instances of the given motif. In this paper, we develop a novel algorithm for counting independent copies of a given motif topology in probabilistic biological networks. We propose a novel mathematical model to capture the dependency between each embedding and all the other embeddings, which it overlaps with. We prove the correctness of this model. Our experiments on real and synthetic networks demonstrate that our method counts non-overlapping embeddings in practical time for a broad range of networks with different probability, and topology models as well as reasonable range of network sizes.

Analysis of handwritten documents is a challenging task in the modern era of document digitization. It requires efficient preprocessing which includes word segmentation and baseline detection. This paper proposes a novel approach toward word segmentation and baseline detection in a handwritten document. It is based on certain structural properties of isothetic covers tightly enclosing the words in a handwritten document. For an appropriate grid size, the isothetic covers successfully segregate the words so that each cover corresponds to a particular word. The grid size is selected by an adaptive technique that classifies the inter-cover distances into two classes in an unsupervised manner. Finally, by using a geometric heuristic with the horizontal chords of these covers, the corresponding baselines are extracted. Owing to its traversal strategy along the word boundaries in a combinatorial manner and usage of limited operations strictly in the integer domain, the method is found to be quite fast, efficient, and robust, as demonstrated by experimental results with datasets of both Bengali and English handwritings.

Analysis of handwritten documents is a challenging task in the modern era of document digitization. It requires efficient preprocessing which includes word segmentation and baseline detection. This paper proposes a novel approach toward word segmentation and baseline detection in a handwritten document. It is based on certain structural properties of isothetic covers tightly enclosing the words in a handwritten document. For an appropriate grid size, the isothetic covers successfully segregate the words so that each cover corresponds to a particular word. The grid size is selected by an adaptive technique that classifies the inter-cover distances into two classes in an unsupervised manner. Finally, by using a geometric heuristic with the horizontal chords of these covers, the corresponding baselines are extracted. Owing to its traversal strategy along the word boundaries in a combinatorial manner and usage of limited operations strictly in the integer domain, the method is found to be quite fast, efficient, and robust, as demonstrated by experimental results with datasets of both Bengali and English handwritings.

A novel two-stage algorithm for constructing the orthogonal concavity tree (OCT) of a digital object is proposed. In Stage I, it derives the minimum-area orthogonal cover of the object. In Stage II, it constructs the orthogonal hull from the ortho-cover, and while doing so, extracts the orthogonal concavities in an iterative manner. Nested concavities, if any, are obtained by considering each concavity and its ortho-hull, and the resultant concavities can be used to prepare the OCT. A smaller grid size captures the finer concavities of the underlying object, whereas a larger grid size results in fewer and coarser concavities. Experimental results demonstrate the efficacy and elegance of the proposed algorithm.