Dataset Information

GASOLINE: a Greedy And Stochastic algorithm for optimal Local multiple alignment of Interaction NEtworks.

ABSTRACT: The analysis of structure and dynamics of biological networks plays a central role in understanding the intrinsic complexity of biological systems. Biological networks have been considered a suitable formalism to extend evolutionary and comparative biology. In this paper we present GASOLINE, an algorithm for multiple local network alignment based on statistical iterative sampling in connection to a greedy strategy. GASOLINE overcomes the limits of current approaches by producing biologically significant alignments within a feasible running time, even for very large input instances. The method has been extensively tested on a database of real and synthetic biological networks. A comprehensive comparison with state-of-the art algorithms clearly shows that GASOLINE yields the best results in terms of both reliability of alignments and running time on real biological networks and results comparable in terms of quality of alignments on synthetic networks. GASOLINE has been developed in Java, and is available, along with all the computed alignments, at the following URL: http://ferrolab.dmi.unict.it/gasoline/gasoline.html.

SUBMITTER: Micale G

PROVIDER: S-EPMC4049608 | biostudies-literature | 2014

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

GASOLINE: a Greedy And Stochastic algorithm for optimal Local multiple alignment of Interaction NEtworks.

Micale Giovanni G Pulvirenti Alfredo A Giugno Rosalba R Ferro Alfredo A

PloS one 20140609 6

The analysis of structure and dynamics of biological networks plays a central role in understanding the intrinsic complexity of biological systems. Biological networks have been considered a suitable formalism to extend evolutionary and comparative biology. In this paper we present GASOLINE, an algorithm for multiple local network alignment based on statistical iterative sampling in connection to a greedy strategy. GASOLINE overcomes the limits of current approaches by producing biologically sig ...[more]

PMID: 24911103

Similar Datasets

Project description:MotivationProtein complexes are one of the keys to studying the behavior of a cell system. Many biological functions are carried out by protein complexes. During the past decade, the main strategy used to identify protein complexes from high-throughput network data has been to extract near-cliques or highly dense subgraphs from a single protein-protein interaction (PPI) network. Although experimental PPI data have increased significantly over recent years, most PPI networks still have many false positive interactions and false negative edge loss due to the limitations of high-throughput experiments. In particular, the false negative errors restrict the search space of such conventional protein complex identification approaches. Thus, it has become one of the most challenging tasks in systems biology to automatically identify protein complexes.ResultsIn this study, we propose a new algorithm, NEOComplex ( NE CC- and O rtholog-based Complex identification by multiple network alignment), which integrates functional orthology information that can be obtained from different types of multiple network alignment (MNA) approaches to expand the search space of protein complex detection. As part of our approach, we also define a new edge clustering coefficient (NECC) to assign weights to interaction edges in PPI networks so that protein complexes can be identified more accurately. The NECC is based on the intuition that there is functional information captured in the common neighbors of the common neighbors as well. Our results show that our algorithm outperforms well-known protein complex identification tools in a balance between precision and recall on three eukaryotic species: human, yeast, and fly. As a result of MNAs of the species, the proposed approach can tolerate edge loss in PPI networks and even discover sparse protein complexes which have traditionally been a challenge to predict.Availability and implementationhttp://acolab.ie.nthu.edu.tw/bionetwork/NEOComplex.Contactbab@csail.mit.edu or csliao@ie.nthu.edu.tw.Supplementary informationSupplementary data are available at Bioinformatics online.

Dataset Information

GASOLINE: a Greedy And Stochastic algorithm for optimal Local multiple alignment of Interaction NEtworks.

Publications

GASOLINE: a Greedy And Stochastic algorithm for optimal Local multiple alignment of Interaction NEtworks.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets