Skip to Main content Skip to Navigation
Conference papers

ComPotts: Optimal alignment of coevolutionary models for protein sequences

Hugo Talibart 1 François Coste 1
1 Dyliss - Dynamics, Logics and Inference for biological Systems and Sequences
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : To assign structural and functional annotations to the ever increasing amount of sequenced proteins, the main approach relies on sequence-based homology search methods , e.g. BLAST or the current state-of-the-art methods based on profile Hidden Markov Models (pHMMs), which rely on significant alignments of query sequences to annotated proteins or protein families. While powerful, these approaches do not take coevolution between residues into account. Taking advantage of recent advances in the field of contact prediction, we propose here to represent proteins by Potts models, which model direct couplings between positions in addition to positional composition. Due to the presence of non-local dependencies, aligning two Potts models is computationally hard. To tackle this task, we introduce an Integer Linear Programming formulation of the problem and present ComPotts, an implementation able to compute the optimal alignment of two Potts models representing proteins in tractable time. A first experimentation on 59 low sequence identity pairwise alignments, extracted from 3 reference alignments from sisyphus and BaliBase3 databases, shows that ComPotts finds better alignments than the other tested methods in the majority of these cases.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-02862213
Contributor : Hugo Talibart <>
Submitted on : Tuesday, June 9, 2020 - 1:26:50 PM
Last modification on : Thursday, January 7, 2021 - 4:14:05 PM

File

jobim_proceedings.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02862213, version 1

Citation

Hugo Talibart, François Coste. ComPotts: Optimal alignment of coevolutionary models for protein sequences. JOBIM 2020 - Journées Ouvertes Biologie, Informatique et Mathématiques, Jun 2020, Montpellier, France. pp.1-8. ⟨hal-02862213⟩

Share

Metrics

Record views

87

Files downloads

249