Parallel seed-based approach to multiple protein structure similarities detection - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Parallel seed-based approach to multiple protein structure similarities detection

(1) , (1) , (1) , (2) , (1)
1
2

Abstract

Finding similarities between protein structures is a crucial task in molecular biology. Most of the existing tools require proteins to be aligned in order-preserving way and only find single alignments even when multiple similar regions exist. We propose a new seed-based ap-proach that discovers multiple pairs of similar regions. Its computa-tional complexity is polynomial and it comes with a quality guarantee– the returned alignments have both Root Mean Squared Deviations (coordinate-based as well as internal-distances based) lower than a given threshold, if such exist. We do not require the alignments to be order preserving (i.e. we consider non-sequential alignments), which makes our algorithm suitable for detecting similar domains when com-paring multi-domain proteins as well as to detect structural repetitions within a single protein. Because the search space for non-sequential alignments is much larger than for sequential ones, the computational burden is addressed by extensive use of parallel computing techniques: a coarse-grain level parallelism making use of available CPU cores for computation and a fine-grain level parallelism exploiting bit-level con-currency as well as vector instructions.
Fichier principal
Vignette du fichier
sp_main.pdf (633.65 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01093809 , version 1 (11-12-2014)

Identifiers

  • HAL Id : hal-01093809 , version 1

Cite

Guillaume Chapuis, Mathilde Le Boudic-Jamin, Rumen Andonov, Hristo Djidjev, Dominique Lavenier. Parallel seed-based approach to multiple protein structure similarities detection . 2014. ⟨hal-01093809⟩
188 View
111 Download

Share

Gmail Facebook Twitter LinkedIn More