Bioinformatický seminár

Tue 9 Apr. 2013, 17:20
I-9

Title: Luqman Hodgkinson, Richard M. Karp (2012) Algorithms to detect multiprotein modularity conserved during evolution
Speaker: Matúš Kempa

Detecting essential multiprotein modules that change infrequently during
evolution is a challenging algorithmic task that is important for understanding
the structure, function, and evolution of the biological cell. In this paper, we 
define a measure of modularity for interactomes and present a linear-time
algorithm, Produles, for detecting multiprotein modularity conserved during
evolution that improves on the running time of previous algorithms for related
problems and offers desirable theoretical guarantees. We present a biologically
motivated graph theoretic set of evaluation measures complementary to previous
evaluation measures, demonstrate that Produles exhibits good performance by all
measures, and describe certain recurrent anomalies in the performance of previous
algorithms that are not detected by previous measures. Consideration of the newly
defined measures and algorithm performance on these measures leads to useful
insights on the nature of interactomics data and the goals of previous and
current algorithms. Through randomization experiments, we demonstrate that
conserved modularity is a defining characteristic of interactomes. Computational 
experiments on current experimentally derived interactomes for Homo sapiens and
Drosophila melanogaster, combining results across algorithms, show that nearly 10
percent of current interactome proteins participate in multiprotein modules with 
good evidence in the protein interaction data of being conserved between human
and Drosophila.