BICTEL/e - ULg

Mouton, Alexandre

CLOES, Marc

GUILLAUME, Jean-Fran\ue7ois

GOSSET, Christiane

BURY, Thierry

BRUYERE, Olivier

GUILLAUME, Mich\ue8le

LECHNER, Lilian

GUISSARD, Nathalie

French

La promotion de lactivit\ue9 physique chez les seniors : approche au sein dune communaut\ue9 locale

Ziegler, Erik

Phillips, Christophe

Geuzaine, Christophe

Multimodal modelling of the human brain

Becker, Julien

Maes, Francis

Geurts, Pierre

Denoyer, Ludovic

Charloteaux, Beno\ueet

Wehenkel, Louis

Dehareng, Dominique

Dissertation for the degree of
Doctor of Philosophy in Computer Science
University of Liège
Protein Structural Annotation
Multi-task learning and feature selection
by Julien Becker
Advisor : Co-advisor :
Prof. Louis Wehenkel Dr. Francis Maes
Summer 2013
Table des matières
1 Introduction 13
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.1 Protein structure prediction . . . . . . . . . . . . . . . . . . . . . . 14
1.1.2 Protein structural annotation . . . . . . . . . . . . . . . . . . . . . 16
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Thesis layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Background in machine learning 21
2.1 An introduction to supervised learning . . . . . . . . . . . . . . . . . . . . 22
2.1.1 Examples of supervised learning tasks . . . . . . . . . . . . . . . . 23
2.1.2 The global architecture of supervised learning algorithms . . . . . 25
2.1.3 Supervised learning and the theory of risk minimization . . . . . . 25
2.2 Stochastic gradient descent for linear models . . . . . . . . . . . . . . . . . 28
2.3 Kernel methods and support vector machines . . . . . . . . . . . . . . . . 30
2.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.2 Common kernel functions . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.3 Beyond support vector machines . . . . . . . . . . . . . . . . . . . 32
2.4 Tree-based ensemble methods for classification . . . . . . . . . . . . . . . . 34
2.5 k-Nearest neighbors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.6 An introduction to feature selection . . . . . . . . . . . . . . . . . . . . . . 40
2.6.1 Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.6.2 Wrappers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.6.3 Embedded methods . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3 Background on structural biology 45
3.1 Fundamentals of protein structure . . . . . . . . . . . . . . . . . . . . . . 46
3.1.1 Chemical bonds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.1.2 Primary structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1.3 Secondary structure . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.4 Tertiary structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1.5 Quaternary structure . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2 Structure determination of biological macromolecules . . . . . . . . . . . . 51
3.2.1 X-ray crystallography . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2.2 Nuclear magnetic resonance spectroscopy . . . . . . . . . . . . . . 52
3.2.3 Electron microscopy . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3 The Protein Data Bank . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.1 Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4 Protein structure-based annotations . . . . . . . . . . . . . . . . . . . . . 55
3.4.1 DSSP secondary structure . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.2 Secondary structure . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.3 Solvent accessibility . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.4 Disordered regions . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4.5 Structural alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.6 Disulfide pattern connectivity . . . . . . . . . . . . . . . . . . . . . 58
4 Iterative multi-task sequence labeling 61
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.1.1 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Materials and methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.2.1 Notations and problem statement . . . . . . . . . . . . . . . . . . . 64
4.2.2 Iterative black-box multi-task learning . . . . . . . . . . . . . . . . 65
4.2.3 Datasets and annotations . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 Multi-task sequence labeling for protein annotations . . . . . . . . . . . . 68
4.3.1 Base sequence-labeling model . . . . . . . . . . . . . . . . . . . . . 68
4.3.2 Features encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5 Feature selection for disulfide connectivity prediction 73
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.1 Disulfide bridge related prediction problems . . . . . . . . . . . . . 76
5.2.2 Features for cysteines and cysteine pairs . . . . . . . . . . . . . . . 77
5.3 Materials and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3.1 Notations and problem statement . . . . . . . . . . . . . . . . . . . 78
5.3.2 Disulfide pattern prediction pipeline . . . . . . . . . . . . . . . . . 80
5.3.3 Forward feature function selection . . . . . . . . . . . . . . . . . . 84
5.4 Disulfide pattern prediction . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.4.1 Comparison of the cysteine pair classifiers . . . . . . . . . . . . . . 86
5.4.2 Feature functions selection . . . . . . . . . . . . . . . . . . . . . . . 87
5.4.3 Evaluation of the constructed prediction pipeline . . . . . . . . . . 90
5.4.4 Sensitivity of ETs to its hyper-parameters . . . . . . . . . . . . . . 92
5.5 Chain classification and cysteine bonding state prediction . . . . . . . . . 92
5.5.1 Chain classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.5.2 Cysteine bonding state prediction . . . . . . . . . . . . . . . . . . . 93
5.5.3 Impact on pattern prediction . . . . . . . . . . . . . . . . . . . . . 94
5.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6 Feature selection for disordered regions prediction 99
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.2 Materials and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.2.1 Datasets and annotations . . . . . . . . . . . . . . . . . . . . . . . 101
6.2.2 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.2.3 Candidate feature functions . . . . . . . . . . . . . . . . . . . . . . 105
6.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3.1 Identification of a set of relevant feature functions . . . . . . . . . 109
6.3.2 Evaluation of the selected feature functions . . . . . . . . . . . . . 111
6.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7 Perspectives and Conclusions 117
7.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.1.1 Multi-task learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.1.2 Feature function selection . . . . . . . . . . . . . . . . . . . . . . . 118
7.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.2.1 A unified architecture for protein structure prediction . . . . . . . 120
7.2.2 A semi-unified architecture for protein structure prediction . . . . 124
Bibliographie 127
Summary
Experimentally determining the three-dimensional structure of a protein is a slow and
expensive process. Nowadays, supervised machine learning techniques are widely used to
predict protein structures, and in particular to predict surrogate annotations, which are
much less complex than 3D structures.
This dissertation presents, on the one hand, methodological contributions for learning
multiple tasks simultaneously and for selecting relevant feature representations, and on
the other hand, biological contributions issued from the application of these techniques
on several protein annotation problems.
Our first methodological contribution introduces a multi-task formulation for learning
various protein structural annotation tasks. Unlike the traditional methods proposed in
the bioinformatics literature, which mostly treated these tasks independently, our frame-
work exploits the natural idea that multiple related prediction tasks should be designed
simultaneously. Our empirical experiments on a set of five sequence labeling tasks clearly
highlight the benefit of our multi-task approach against single-task approaches in terms
of correctly predicted labels. Our second methodological contribution focuses on the best
way to identify a minimal subset of feature functions, i.e., functions that encode properties
of complex objects, such as sequences or graphs, into appropriate forms (typically, vectors
of features) for learning algorithms. Our empirical experiments on disulfide connectivity
pattern prediction and disordered regions prediction show that using carefully selected
feature functions combined with ensembles of extremely randomized trees lead to very
accurate models.
Our biological contributions are mainly issued from the results obtained by the appli-
cation of our feature function selection algorithm on the problems of predicting disulfide
connectivity patterns and of predicting disordered regions. In both cases, our approach
identified a relevant representation of the data that should play a role in the predic-
tion of disulfide bonds (respectively, disordered regions) and, consequently, in protein
structure-function relationships. For example, the major biological contribution made by
our method is the discovery of a novel feature function, which has - to our best know-
ledge - never been highlighted in the context of predicting disordered regions. These
representations were carefully assessed against several baselines such as the 10th Critical
Assessment of Techniques for Protein Structure Prediction (CASP) competition.
Résumé
Déterminer la structure tridimensionnelle des protéines de manière expérimentale est
un processus lent et coûteux. De nos jours, pour palier ces difficultés, les techniques
d’apprentissage automatique supervisé se sont fortement développées dans le domaine
de la prédiction des structures de protéines, et plus particulièrement pour prédire des
annotations partielles sous-jacentes à la structure 3D, quoique moins complexes.
Cette thèse présente, d’une part, des contributions méthodologiques dans le domaine
de l’apprentissage multitâches (multi-task learning), où l’objectif est d’apprendre plu-
sieurs tâches simultanément, ainsi que dans le domaine de la sélection de représentations
pertinentes (feature selection), c’est-à-dire, des représentations capables d’extraire l’es-
sence de l’information utile pour le problème de prédiction considéré. D’autre part, cette
thèse présente également des contributions biologiques directement issues de l’application
de nos méthodes à divers problèmes d’annotation de protéines.
Notre première contribution méthodologique réside dans la formulation multitâche
de problèmes d’annotation liés à la prédiction de la structure des protéines. Dans la lit-
térature bioinformatique, les problèmes d’annotation des protéines sont habituellement
traités de manière indépendante. Or, au vu du lien fort qui unit ces différentes tâches,
nous avons développé une méthodologie qui exploite l’idée que des tâches qui semblent
liées entre-elles devraient être traitées simultanément. Nos expériences, menées sur un
ensemble de cinq problèmes d’annotation de séquences liés à la prédiction de la struc-
ture des protéines, nous ont permis de clairement mettre en évidence l’intérêt de notre
approche multitâche comparée à une approche qui ne traite qu’une seule tâche à la fois.
Notre seconde contribution sur le plan méthodologique se focalise sur la manière d’iden-
tifier une représentation pertinente pour un problème particulier, où une représentation
“pertinente” est définie comme un sous-ensemble minimal de jeux de variables (feature
functions) permettant de réaliser la tâche de prédiction considérée. Dans ce contexte, un
jeu de variables permet d’encoder une information particulière d’intérêt d’une séquence
ou d’un graphe, sous un format exploitable par des algorithmes d’apprentissage automa-
tique (généralement, un vecteur de nombres). Nos expériences pour déterminer le meilleur
moyen de représenter les protéines pour la prédiction du motif formé par les ponts disul-
fures, ainsi que sur le meilleur moyen de représenter les protéines pour la prédiction de
régions dites désordonnées, nous ont permis de montrer qu’une représentation soigneu-
sement choisie combinée avec des ensembles d’arbres extrêmement aléatoires permettait
d’obtenir des modèles prédictifs très performants par rapport à l’état de l’art.
Notre contribution biologique résulte de l’application de notre méthodologie de sé-
lection de jeux de variables. Dans les deux études que nous avons menées (à savoir, la
prédiction du motif formé par les ponts disulfures et la prédiction de régions désordon-
nées), notre approche nous a permis d’identifier des représentations pertinentes pour
l’apprentissage de modèles prédictifs et ainsi d’aider à la compréhension de la relation
structure-fonction des protéines. Par exemple, notre contribution principale au niveau bio-
logique est la découverte d’un nouveau jeu de caractéristiques qui, à notre connaissance,
n’ont encore jamais été mis en évidence dans le cadre de la prédiction de régions désor-
données. La pertinence de ce nouveau jeu caractéristiques a été rigoureusement évaluée
par rapport à plusieurs points de comparaison dont la 10ème édition de la compétition
CASP (Critical Assessment of Techniques for Protein Structure Prediction).


Protein Structural Annotation: Multi-task learning and feature selection

Paeme, Sabine

Geris, Liesbet

Desaive, Thomas

Ponthot, Jean-Philippe

Mathematical modeling of the mitral valve. From local to global hemodynamics

Molina Marmol, Ma\ueft\ue9

Ribert, Evelyne

Strivay, Lucienne

Martiniello, Marco

Havelange, Carl

Lillo, Natacha

Migration, m\ue9moire, patrimonialisation. \uc9tude empirique de la m\ue9moire collective de l'exil et de l'immigration espagnols en Belgique

Fradi, Ines

CATALDO, Didier

KALLEL, Mohammed

FILLET , Marianne

HUBERT, Philippe

VAN SCHEPDAEL, Ann

SERVAIS, Anne-Catherine

ELFAKIR, Claire

BEN RAYANA, Mohamed

CROMMEN, Jacques

In-line derivatization of D and L amino acids by capillary electrophoresis/D\ue9rivatisation en ligne et s\ue9paration d'acides amin\ue9s D et L par \ue9lectrophor\ue8se capillaire

Caron, Nicolas

ROGISTER, Bernard

MALGRANGE, Brigitte

BAKKER, Julie

DEMENEIX, Barbara

GOFFLOT, Fran\ue7oise

NGUYEN, Laurent

PARENT, Anne-Simone

Etude du r\uf4le de Cdk4 et Cdk6 dans la neurogen\ue8se postnatale/adulte

Bournine, Lamine

BELLAHCENE, Akeila

FREDERICH, Michel

BEDJOU, Fatiha

MAIZA-BENABDESSELAM, Fadila

TOUATI, Abdelaziz

Contribution \ue0 l'\ue9tude phytochimique et \ue0 l'\ue9valuation du potentiel anti-canc\ue9reux de Glaucium flavum, une plante utilis\ue9e en m\ue9decine traditionnelle alg\ue9rienne/Contribution to the phytochemical study and evaluation of the anti-cancer potential of Glaucium flavum, a plant used in Algerian traditional medicine

Nahayo, Adrien

ROLLIN, Fr\ue9d\ue9ric

MAINIL, Jacques

LOSSON, Bertrand

LIBOIS, Roland

HADDAD, Nadia

COIGNOUL, Freddy

CLAEREBOUT, Edwin

LINDEN, Annick

GILLET, Laurent

SAEGERMAN, Claude

Contribution \ue0 l\ue9tude \ue9pid\ue9miologique dAnaplasma phagocytophilum chez des cervid\ue9s et suid\ue9s sauvages en R\ue9gion wallonne.

Burmistrova, Anastasia

Bouju, Xavier

Dufrene, Yves

Gabelica, Val\ue9rie

De Pauw, Edwin

Leyh, Bernard

Duwez, Anne-Sophie

Remacle, Fran\ue7oise

Investigation on the dissociation mechanisms of short DNA duplexes under external constraint and in the presence of ligands