A multi-objective optimization approach accurately resolves protein domain architectures

Abstract

Motivation: Given a protein sequence and a number of potential domains matching it, what are the domain content and the most likely domain architecture for the sequence? This problem is of fundamental importance in protein annotation, constituting one of the main steps of all predictive annotation strategies. On the other hand, when potential domains are several and in conflict because of overlapping domain boundaries, finding a solution for the problem might become difficult. An accurate prediction of the domain architecture of a multi-domain protein provides important information for function prediction, comparative genomics and molecular evolution.

Results: We developed DAMA (Domain Annotation by a Multi-objective Approach), a novel approach that identifies architectures through a multi-objective optimization algorithm combining scores of domain matches, previously observed multi-domain co-occurrence and domain overlapping. DAMA has been validated on a known benchmark dataset based on CATH structural domain assignments and on the set of Plasmodium falciparum proteins. When compared with existing tools on both datasets, it outperforms all of them.

Availability and implementation: DAMA software is implemented in C++ and the source code can be found at http://www.lcqb.upmc.fr/DAMA.

Contact: juliana.silva_bernardes@upmc.fr or alessandra.carbone@lip6.fr

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

Main steps in DAMA algorithm. (A) Potential domains ($\mathcal{P}$) for a query sequence are ranked from bottom to top by their decreasing E value. Overlaps between domains are allowed (see domains de or dg). Domains are denoted with different letters. The same letter code is used in (B–E). (B) Domains in (A) are represented as nodes of an ‘interval’ graph, where edges connect all overlapping domains with the exception of domains with a very small overlap or domains that appear as overlapping in the list of known protein architectures in (C) (see the overlapping condition). Edges not included in G are (g, d) because the overlap is too small and (a, c) because the overlap is known (see C). (C) List of known domain architectures sharing domains with $\mathcal{P}$. (D) List of all Maximal Independent Subsets associated to some domain (MSI) for the graph in B satisfying pairwise domain constraints according to the list in (C). (E) List of feasible architectures obtained by crossing information coming from (C) and (D). (F) Filtering of the architectures in E with 5 optimization functions and selection of the best architecture

Fig. 2.

Selection of architectures with a multiple domain co-occurrence. (A) Two architectures, A₁, A₂, where A₁ is composed by a double occurrence of domain b. Domains are denoted with different letters, and the same letter code is used in (B) and (C). (B) List of architectures that allow for the selection of A₁ with the objective function F₂, because $F_2(abb)=3$ and $F_2(abc)=2$. (C) List of architectures that allow for the selection of A₂ with the objective function F₄, because $F_4(abb)=2$ and $F_4(abc)=3$. Note that $F_2(abb)=F_2(abc)=2,\hspace{0.17em}{F}_3(abb)=F_3(abc)=3$

Fig. 3.

Performance of DAMA and other tools on the P. falciparum proteins annotation. (A) The y-axis is the number of predicted domains per protein (‘signal’), while the x-axis is the FDR (‘noise’), so better performing methods have higher curves (more signal for a given noise threshold). On the 1-mer and the 4-mer hypotheses, DAMA (red) outperforms all hmmscan variations tested (black) and the methods MDA (pink), dPUC (blue) and CODD (green). (B) The y-axis is the number of certified domains (‘signal’) obtained by a method, while the x-axis is the FDR (‘noise’) computed over domain architectures. Colors as in (A). (C) Distribution of the number of proteins with a fixed number of predicted domains, for each tool at FDR $=2e$-4 (see vertical bar in A) for 1-mer and at FDR $=9e$-4 for 4-mer. (D) Distribution of number of proteins with a fixed number of predicted domains, for each tool at FDR $=0.05$ (see vertical bar in B)

Fig. 4.

Three examples of domain predictions on P. falciparum proteins. Architectures of P. falciparum proteins identified by DAMA, CODD, dPUC, MDA run with default parameters. DAMA shows to identify more domains that other tools and predictions are based on known co-occurrence in Pfam₂₇: (A) DEAD, SPRY, Helicase_C co-occur in 113 proteins; (B) RRM_5 (2 occurrences), RRM_1, RRM_6 co-occur in 34 proteins; (C) CDC48_N, CDC48_2, AAA x 2, Vps4_C co-occur in 159 proteins. The name of the protein (PlasmDB id) is followed by its length (number of amino-acids). DAMA was used fixing a FDR threshold at 2e–04, as in the 1-mer experiment reported in Figure 3C