# Réseaux d'interaction protéine/protéine

Les réseaux d'interaction protéine-protéine (IPP), de la génération du réseau à sa visualisation, de l'extraction des métriques à la compréhension de la topologie ou à la détection des communautés, trouve son importance entre autres dans la compréhension des pathologies, la fonction des protéines.

## Les réseaux en Biologie

Les systèmes biologiques sont extrêmement complexes. Les processus biologiques à l’intérieur des cellules caractérisés entre autres par les interactions entre les molécules qui s’y trouvent ne peuvent être compris en étudiant molécule par molécule car elles fonctionnent souvent de manière différente suivant le mécanisme dans lequel elles sont impliquées.. Aussi, de nouvelles caractéristiques biologiques absentes dans des composants isolés apparaissent selon le type d’interaction entre ces composants. Ce qui explique l'intérêt pour les réseaux d’interactions, dont l’un des principaux défis consiste à comprendre et à analyser leurs structures et leurs dynamiques. Les techniques de collecte de données à haut débit, le développement des bases de données moléculaires (protéines, gènes, métabolites…) facilitent l’étude et la génération de plusieurs types de réseaux biologiques.
Les réseaux biologiques sont généralement classés selon la nature des molécules impliquées.

### Réseaux de régulation des gènes

La transcription d’un gène en ARNm est régulée par les facteurs de transcriptions (FT), protéines avec au moins un domaine de liaison à l’ADN. En se liant à ces domaines, les FT activent ou inhibent la production d’une autre protéine. Dans les organismes unicellulaires, les réseaux de régulation des gènes sont essentiels pour réguler l’activité cellulaire afin de survivre aux conditions environnementales externes. Dans les organismes multicellulaires, ces réseaux servent à l’activité cellulaire en fonction de la fonction particulière que la cellule doit remplir. Trois types de modèles ont été proposés pour les réseaux de régulation des gènes.
* Modèle logique ou booléen: description des réseaux de régulation d’un point de vue qualitatif pour comprendre si un gène est activé ou non à un moment donné de la vie du système
* Modèle continu: description des réseaux d’un point de vue quantitatif (concentration des molécules…)
* Modèles à molécule unique: sur le bruit qui affectent la fonctionnalité des réseaux

### Réseaux de signalisation

Les cellules ont la capacité de recevoir et de traiter des signaux qui proviennent de l'extérieur afin de répondre aux changements dans leur environnement immédiat. Cette communication est rendue possible par des réseaux de signalisation et de transduction cellulaires. On en distingue 5 classes: intracrine, autocrine, juxtacrine, paracrine, endocrine selon l’origine et la cible des signaux, et 3 classes selon la molécule de signalisation (hormones, neurotransmetteurs, cytokines).

### Réseaux métaboliques

Ils représentent l’ensemble des réactions métaboliques de la cellule. Un réseau complet de plusieurs organismes, des bactéries à l’homme, peuvent être reconstruits grâce au séquençage et d’ailleurs plusieurs de ces réseaux sont disponibles dans plusieurs bases de données telles que KEGG. Il existe des réseaux métaboliques simplifiés (réaction, enzyme, substance), des réseaux de métabolites (uniquement de substances) et métabolites simplifiés (substances principales) ainsi que des réseaux d’enzymes

### Réseaux de co-expression des gènes

Ils permettent d’identifier les gènes qui sont contrôlés par la même régulation transcriptionnelle qui sont fonctionnellement liés, ou dont les gènes sont impliqués dans un processus biologique commun. Ces réseaux ne fournissent cependant aucune information sur les relations de causalité entre les gènes (activation ou inhibition). Ils sont constitués en 2 étapes principales: calcul d’une mesure de co-expression (matrice d’expression) et sélection d’un seuil de significativité (coefficient de corrélation de Pearson, distance euclidienne, corrélation de Spearman...).

### Réseaux IPP

Les protéines sont les principaux agents de la fonction biologique. Elles contrôlent les mécanismes moléculaires et cellulaires et par conséquent, déterminent les états sains et malades des organismes. Toutefois, elles ne sont pas fonctionnelles sous forme isolée, mais elles interagissent entre elles et avec d'autres molécules (par exemple, l'ADN et l'ARN) pour remplir leurs fonctions. Ainsi, l'étude des interactions des protéines est cruciale pour comprendre leur rôle à l'intérieur de la cellule. Comme ce type d'interactions peut être de plusieurs types, le terme d'interaction protéine-protéine fait référence à une variété d'événements se produisant à l'intérieur de la cellule.
En biologie moléculaire, un interactome est l'ensemble des interactions moléculaires dans une cellule particulière. Dans le cas des protéines, également connues sous le nom d’interactions protéines-protéines IPP. Les interactions basées sur les IPP doivent être associées au protéome de l'espèce correspondante afin de fournir une vue globale ("omique") de toutes les interactions moléculaires possibles qu'une protéine peut présenter.
Un réseau d'interaction protéine-protéine stocke les informations sur l'interactome protéine-protéine d'un organisme donné, c'est-à-dire l'ensemble de ses interactions protéine-protéine. Il a été suggéré que la taille des interactomes protéine-protéine augmente proportionnellement à la complexité biologique des organismes, aucun interactome protéine-protéine n'a été complètement identifié et, par conséquent, cette corrélation ne reste qu'une conjecture. En outre, les réseaux d'interaction protéine-protéine disponibles sont sujets à des erreurs, car les méthodes expérimentales utilisées pour découvrir les interactions peuvent inclure des faux positifs ou ne pas révéler certaines interactions existantes. Malgré cela, les réseaux d’interaction protéine-protéines sont particulièrement important dans de nombreux contextes:
* l'analyse de ces réseaux facilite la compréhension des mécanismes qui déclenchent le début et la progression des maladies
* les réseaux d'interaction protéine-protéine ont été utilisés pour découvrir de nouvelles fonctions des protéines et pour identifier des modules fonctionnels et des modèles d'interaction conservés.
* certains travaux sur la structure des réseaux d'interaction protéine-protéine de plusieurs espèces ont permis de découvrir que, indépendamment de l'espèce, les réseaux d'interaction protéine-protéine sont sans échelle. Cela signifie que certaines protéines "hub" ont un rôle central participant à la majorité des interactions alors que la plupart des protéines, qui ne sont pas des "hubs", ne participent qu'à une petite fraction des interactions

## Les sources de données

Les réseaux IPP sont un des types de réseaux biologiques, et se rejoignent sur les ressources utilisées pour leur réalisation. Ceci est la première étape pour construire un réseau. Il existe différentes sources de données IPP qui peuvent être utilisées pour ce faire et il est important de connaître leurs avantages et leurs inconvénients.
Vous pouvez obtenir des données IPP de:
Vos propres travaux expérimentaux, où vous pouvez choisir la manière dont les données sont représentées et stockées
Une base de données IPP primaire. Ces bases de données extraient les IPP à partir des preuves expérimentales rapportées dans la littérature en utilisant un processus de traitement manuel. Elles sont les principaux fournisseurs de données sur les IPP et peuvent représenter beaucoup de détails sur les interactions, selon la base de données.
Une base de métadonnées ou une base de données prédictive. Ces ressources rassemblent les informations fournies par différentes bases de données primaires et fournissent une représentation unifiée des données à l'utilisateur. Les bases de données prédictives vont plus loin et utilisent les ensembles de données produites expérimentalement pour prédire par calcul les interactions dans les zones inexplorées de l'interactome. Les bases de données prédictives offrent un moyen d'élargir ou d'affiner l'espace des interactions dérivées expérimentalement, mais les ensembles de données produits sont plus bruyants que ceux provenant d'autres sources
Base de données pour réseaux IPP
Il existe plusieurs base de données pour construire des réseaux IPP. On peut citer
* BioCyc , KEGG, Reactome, DIP, STRING.
Plus de détails sur Protein–Protein Interaction Databases

## Topologie et métriques des réseaux

La théorie des réseaux complexes se base sur le principe que toutes les interactions, qu’elles soient physiques ou fonctionnelles, peuvent être conceptualisées sous la forme abstraite d’un réseau, composé de nœuds et de liens. Chaque nœud représente un élément du réseau, et chaque lien une interaction.
Un réseau peut être orienté ou non orienté. Dans le cas d’un réseau orienté, l’interaction entre deux nœuds est dirigée.
Cette approche a démontré qu’il existe des lois universelles communes à la plupart des réseaux complexes$^,$. Ainsi, les réseaux biologiques partagent les mêmes caractéristiques que d’autres systèmes complexes tels que les puces informatiques ou Internet.
Cette notion permet de caractériser dans l’espace, la géométrie des réseaux IPP. De là, plusieurs méthodes de mesures peuvent être calculées.

## Mesures quantifiables

Il existe plusieurs mesures quantifiables pour caractériser un réseau et faciliter la conceptualisation de systèmes complexes tels que les interactions entre molécules (ex : réaction enzyme/substrat) :

### Le degrés k

Le degrés k d’un nœud indique combien ce nœud a de liens avec d’autres nœuds.

### La distribution des degrés P (k)

P(k) donne la probabilité qu'un nœud ait exactement k liens. P (k) est obtenu en divisant le nombre nœuds avec k liens et en par le nombre total de nœuds.

### Le degré exposant γ

Si la distribution des degrés d’un réseau suit une loi de Poisson, alors P(k) est proportionnel à k-γ. Plus γ est petit, plus les hubs ont un rôle important dans le réseau. Pour une valeur de γ supérieure à 3, les hubs ne sont plus significatifs.

### Chemin le plus court et longueur moyenne du chemin

La distance dans les réseaux est mesurée avec la longueur du chemin, qui nous indique combien de liaisons nous devons traverser pour nous déplacer. Il existe de nombreux chemins possibles entre deux nœuds. Le chemin le plus court est celui avec le plus petit nombre de liens entre les nœuds sélectionnés. On peut calculer le plus court chemin moyen entre toutes les paires de nœuds pour mesurer la navigabilité globale d’un réseau.

### La Betweenness B

C’est une mesure permettant d’analyser la centralité des nœuds d’un réseau et est basée sur les plus courts chemins. Celle-ci indique le nombre de plus courts chemins passant par le nœud considéré. Ainsi, il est possible de déterminer si le nœud contrôle ou non le flux d’informations d’un réseau (plus la fréquence de passage à ce nœud est élevée, plus il contrôle le réseau).

### Le Coefficient de clustering

Si les nœuds A et B et B et C sont respectivement connectés, alors il est très probable que A et C le soient aussi. Ce phénomène peut être quantifié à l'aide du coefficient de clustering CI :
    $C_{I}={\frac {2n_{I}}{k}}\left(k-1\right)$
Avec nI, le nombre de liens reliant les k voisins du nœud I entre eux. En d’autres termes, CI donne le nombre de “triangles” qui passent par le nœud I. Le coefficient de clustering moyen d’un réseau caractérise donc la tendance générale des nœuds à former des clusters ou groupes. Une mesure importante de la structure du réseau est la fonction C (k), qui est définie comme le coefficient de clustering moyen de tous les nœuds avec k liaisons. Un C (k) proportionnel à k - 1, un réseau de type hiérarchique$^,$.
Le degré moyen, la longueur moyenne du chemin, et le coefficient de clustering moyen dépendent du nombre de nœuds et de liens du réseau. En revanche, les fonctions P (k) et C (k) sont indépendantes de la taille du réseau ce qui permet de les utiliser pour classer les réseaux.

## Les différents réseaux

Depuis des décennies, la théorie des graphes permet, grâce aux mathématiques fondamentales, de modéliser des systèmes complexes en objets géométriques réguliers ou en réseaux aléatoires. C’est en 1960 que Paul Erdös et Alfred Rényi initient l’étude des propriétés mathématiques des réseaux, permettant ainsi leur classification (cf. figure 2):

### Les réseaux aléatoires

Caractérisés par un nombre fixe de nœuds connectés aléatoirement. La distribution des degrés des nœuds suit une loi de Poisson . La plupart des nœuds ont donc le même nombre de liens, ce qui permet d’établir un nœud typique du réseau, mais ce qui n’explique pas la topologie des réseaux réels.

### Les réseaux scale-free (sans échelle)

Ces derniers suivent une loi de Puissance. Quelques nœuds centralisent la majorité des liens et constituent un hub. Il n’y a donc pas de nœud consensus qui permettrait de caractériser tous les nœuds du réseau. Quel que soit le règne ou l’organisme, les réseaux cellulaires sont de type scale free dirigés, où les nœuds sont des métabolites et les liens représentent les réactions biochimiques.

### Les réseaux hiérarchiques

Pour tenir compte de la modularité, du clustering local et de la topologie sans échelle dans de nombreux systèmes réels, il faut supposer que les clusters se combinent de manière itérative, générant un réseau de type hiérarchique$^,$. La particularité de ce type de réseau est que le coefficient de clustering C(k) est inversement proportionnel à k-1.

## Caractéristiques des réseaux IPP

Une propriété à retenir des réseaux IPP c’est qu’ils ne sont pas fixes. En effet, il peut y avoir des gains ou pertes de nœuds avec les liens dédiés qui sont provoqués par des évènements génétiques. Pour illustrer cela des mutations, insertions ou même des duplications peuvent induire le rajout de nœuds avec les liens impliqués ou alors les pertes de gènes amènent à la perte des nœuds et liens. D’autres événements peuvent modifier une partie de l’expression et à la régulation d’un gène et ainsi contrôler une partie de gain et de pertes d’interactions. Il a été supposé que la taille du génome pouvait influencer le nombre d’interactions au sein d’un réseau.
Par la suite, il est important de noter qu’un réseau IPP n’est pas le même dans le temps et dans l’espace en raison de la répartition des protéines et que ce dernier change constamment. Les réseaux IPP sont très dynamiques.

### Topologie de réseau

Plusieurs études$^,$ ont démontré que les réseaux d’interactions protéines/protéines sont de type scale-free (exemple: figure 3 - réseau IPP de Saccharomyces Cerevisiae). C’est aussi le cas des réseaux de régulations génétiques. Cependant, tous les réseaux intra-cellulaires ne sont pas de type scale-free. Par exemple, les réseaux de régulation de la transcription de S.Cerevisiae et Escherichia coli offrent un exemple de caractéristiques mixtes.
L’étude des réseaux métaboliques a montré qu’une perturbation locale pouvait affecter rapidement tout le réseau du fait de l’interconnexion quasi totale des métabolites.
L’ensemble des réseaux biologiques de type scale-free suivent un principe dissortatif, c’est-à-dire que les hubs vont avoir tendance à se connecter à des protéines intermédiaires isolées, plutôt qu’à se connecter directement entre eux.
Dans le cadre des réseaux d’interaction protéines/protéines, des comparaisons inter-génomiques ont prouvé que les protéines les plus anciennes sont impliquées dans plus de liens que leurs homologues plus jeunes$^,$. Il y a donc un phénomène évolutif des réseaux d’interaction complexes.

## Visualisation des réseaux IPP

Les réseaux IPP d’une cellule entière sont très rares dans les publications scientifiques à cause de leur complexité visuelle et de gestion. Néanmoins, au fil des années, les scientifiques étudient ces réseaux de différentes manières. Pour la visualisation des réseaux, le logiciel Cytoscape est très largement utilisé pour tous types de réseaux dont ceux des interactions Protéine-Protéine.
Cytoscape est un logiciel open source bio-informatique qui permet la visualisation des réseaux d'interactions moléculaires et l'intégration des profils de gènes ou d'autres données d'état.

## Détection des communautés
### Notion de modularité

Les fonctionnalités cellulaires s’organisent en module. Un module est constitué par un groupe de molécules liées physiquement ou fonctionnellement, et qui agissent ensemble. On peut citer en exemple les complexes inter-protéiques invariants, les complexes ARN/protéine, ou encore les groupes de protéines qui sont liés par une action temporelle commune (ex : régulateurs du cycle cellulaire).
La plupart des molécules cellulaires sont impliquées dans un complexe modulaire. L’utilisation du coefficient de clustering est utile pour étudier la modularité des réseaux : plus le coefficient est élevé, plus le réseau comporte de modules. C’est le cas des réseaux cellulaires, en particulier les inter-protéiques ainsi que les réseaux d’interaction de domaines protéiques.
Les clusters, les hubs, et les modules coexistent au sein du réseau. Les modules ne sont donc pas indépendants, et se combinent en réseau hiérarchique$^,$. L’identification des modules impliqués dans les fonctionnalités cellulaires est une des clefs du développement des réseaux biologiques à venir. La plupart des méthodes de clustering permettent d’identifier les modules d’un réseau, si ces derniers sont clairement séparés. D’autres méthodes, qui combinent critères topologiques et données génomiques permettent de traiter les cas plus complexes$^,$

### Sous-graphs, motifs et clusters de motifs

Alors que les caractéristiques des réseaux hiérarchiques et scale free mettent l'accent sur les principes d'organisation qui déterminent la structure à grande échelle du réseau, une approche alternative commence par le bas et recherche des modèles d'interactions qui caractérisent des réseaux spécifiques.
* Les sous-graphs: un sous-graph représente un sous-ensemble de nœuds qui sont connectés les uns aux autres selon un schéma spécifique (cf. figure 4). Le nombre de sous-graphs distincts croît de façon exponentielle avec le nombre de nœuds.
* Les motifs: les sous-graphs n’ont pas tous la même fréquence d’apparition. Un sous-graph qui apparaît plus fréquemment que sa fréquence aléatoire obtenue par randomisation du réseau, constitue un motif du réseau.
* Les clusters de motifs: les sous-graph et motifs d’un réseau ne sont pas indépendants. Dans l’exemple de la figure 3D (réseau de régulation de la transcription d’E.coli), les motifs se regroupent en cluster. Un seul motif en bas à gauche est isolé.

### Les outils de détection des communautés
#### MCode

MCODE est l'un des premiers algorithmes explicitement conçus pour regrouper les réseaux IPP. MCODE est organisé en quatre phases. Dans la première phase, chaque nœud v se voit attribuer un poids qui est le produit du coefficient de regroupement des noyaux de v et la valeur maximale k pour laquelle il existe un noyau k dans N G (v). Les nœuds sont classés par valeurs décroissantes de leur poids et utilisés comme semences dans cet ordre pour la phase suivante. Dans la deuxième phase, en partant du nœud inutilisé le plus élevé en rang, MCODE ajoute itérativement voisins de la grappe en cours de construction, à condition que leur poids soit supérieur à une fraction fixe du poids de la graine. Les nœuds ajoutés sont marqués comme étant utilisés. Dans la troisième phase, les groupes qui ne comportent pas de noyau double sont rejetés et il est possible d'augmenter le se groupent avec les nœuds voisins au-dessus d'une certaine fraction fixe du poids de la graine. Ces nœuds supplémentaires ne sont pas marqués comme étant utilisés, Ils peuvent donc être partagés entre plusieurs communautés. L'étape finale consiste à calculer le plus grand noyau connecté de chaque candidat.

#### C-finder

C-Finder est un programme rapide qui met en œuvre la méthode CPM (Clique Percolation Method) pour le regroupement des graphiques. L'algorithme fonctionne en deux phases principales. La première phase consiste à trouver tous les k-cliques dans le réseau d'entrée, puis CFinder associe deux k-cliques si elles partagent une (k 1)-clique commune. Les clusters produits par CFinder sont les classes d'équivalence de cette relation d'association. Notez que les groupes distincts produits peuvent partager des nœuds, et l'intersection de deux groupes peut contenir des (k 2)-cliques mais jamais une (k 1)-clique. CFinder a été l'un des premiers algorithmes de clustering qui a pu contrôler étroitement la structure de chevauchement de la famille de clusters qu'il produit. Le paramètre k est critique et pour les applications biologiques, une valeur de l'ordre de k1⁄4 4,5,6 est suggérée dans la publication originale.

#### CMC

L'algorithme CMC (Clustering Based on Maximal Cliques) fonctionne avec des graphes pondérés par les bords. CMC commence par lister toutes les cliques maximales dans un graphe G en utilisant l'algorithme de Tomita et al. (2006), une variante rapide de la méthode de Bron-Kerbosch. Dans la phase suivante, chaque clique maximale reçoit un score qui correspond à son poids moyen à la limite, et ces grappes sont classées par ordre décroissant de valeur de score. Dans la phase suivante, pour chaque groupe C i, les algorithmes considèrent tour à tour les groupes C j de valeur inférieure et décide de fusionner C i et C j (ou de supprimer C j ) sur la base de l'importance relative de leur chevauchement et d'une pondération inter-fonction de score de cluster.
Il existe aussi d’autres algorithmes tels que : Coach, SPICI and ClosterOne, ProBank et Core & Peel (voir plus Pellegrini & all. Community Detection in Biological Networks.

## Alignement des réseaux IPP

L'objectif ultime de l'alignement des réseaux est de transférer la connaissance de la fonction des protéines d'une espèce à l'autre en alignant deux réseaux d'IPP et ainsi de compléter la similarité de séquence par des informations topologiques afin d'identifier les orthologues aussi précisément que possible. En supposant que nous avons k graphes et que chaque graphe a n nœuds, chaque tuple contient k nœuds, un de chaque graphe. Idéalement, nous devrions avoir n tuplets dans l'alignement global avec la stipulation qu'une valeur métrique d'alignement est optimisée.

### Méthodes d'évaluation

De nos jours, aucune solution optimale est inconnue pour l'alignement de réseaux IPP. De ce fait, il devrait y avoir une méthode pour évaluer les divers résultats extraits à l'aide de différents aligneurs. Deux gros ensembles de mesures d'évaluation sont ainsi utilisés pour évaluer la qualité des alignements.
La première série évalue la qualité des caractéristiques topologiques de l'alignement. Le second ensemble mesure l'essence de l'alignement en tenant compte de l'ajustement biologique.

#### Évaluation topologique
##### Correction des bords (EC : edge correctness)

La correction des bords est la mesure la plus populaire utilisée pour mesurer la qualité topologique des alignements de réseaux. La EC calcule le pourcentage d'arêtes du premier réseau qui sont cartographiées, aux arêtes du second réseau.

###### Structure conservée induite (ICS : induced conserved structure)

Pour pallier les faiblesses de la EC, le score ICS a été introduit pour contourner les nœuds d'alignement du premier réseau vers les régions denses du second réseau où les possibilités d'alignement de différentes manières sont élevées. Le score ICS pénalise un tel alignement alors que la EC ne le fait pas.

###### Score de sous-structure symétrique (S3 : symmetric substructure score)

Alors que le SCI s'attaque à une faiblesse de la EC en pénalisant les alignements clairsemés à denses, il ne punit pas de la même façon les alignements denses à clairsemés. Pour améliorer la situation, le score de sous-structure symétrique pénalise de la même manière les alignements clairsemés à denses et denses à clairsemés. Dans les alignements méta-heuristiques, il a été démontré que cette mesure est un prédicteur plus fiable d'un alignement correct que la EC et l'ICS.

###### Plus grande sous-composante commune connectée (LCCS : Largest common connected sub-component)

La taille de la plus grande sous-composante commune connectée considère que de grandes sous-graphiques connectées sont souhaitables. Des scores EC, ICS ou S3 élevés ne reflètent pas nécessairement le fait que les nœuds alignés forment une sous-structure connectée.

###### Correction des nœuds (NC : Node correctness) et des interactions (IC : Interaction Correctness)

Deux autres mesures d'évaluation exigent que le véritable alignement de deux réseaux IPP soit connu afin d'estimer la qualité de l'alignement extrait. Si l'alignement est réel, alors la correction des nœuds (NC) est le pourcentage de nœuds alignés correctement. De même, la correction des interactions (IC) est définie comme le pourcentage d'interactions (c'est-à-dire les bords) correctement cartographiées$^,$.
L'évaluation des alignements sur la base de la qualité topologique n'est pas toujours suffisante. L'évaluation des alignements basée uniquement sur des mesures topologiques ne signifie pas que la qualité de l'alignement est certainement bonne. L'alignement doit être évalué de manière à confirmer que les protéines alignées correspondent à des modules fonctionnels conservés au cours de l'évolution.

#### Évaluation biologique

Les mesures biologiques évaluent la qualité de l'alignement par rapport aux similitudes fonctionnelles entre les deux nœuds (protéines) qui sont cartographiés l'un par rapport à l'autre.

##### Ontologie des gènes (GO : gene ontology)

Les alignements utilisent généralement les annotations de l’ontologie génétique afin de juger de la similarité fonctionnelle des nœuds alignés. Les annotations de l'ontologie des gènes pour chaque protéine sont collectées et comparées pour voir si elles représentent des fonctions similaires$^,$.
La façon naïve d'évaluer le chevauchement des termes GO consiste à rapporter directement le pourcentage de paires de protéines alignées dans l'alignement qui partagent plus de k annotations GO$^,$.

##### La similarité sémantique de Resnik

La mesure de similarité sémantique de Resnik, est l'une des mesures de similarité ontologique les plus courantes qui prend en compte la structure hiérarchique, utilisée afin de concevoir une mesure biologique pour évaluer les alignements de réseaux biologiques. La structure hiérarchique de l'ontologie GO a été prise en compte pour calculer la similarité$^,$.

##### Cohérence de l'ontologie des gènes (GOC: gene ontology consistency)

GOC utilise les annotations GO pour évaluer la qualité de l’alignement.

##### Cohérence normalisée de l'ontologie des gènes (NGOC: normalized gene ontology consistency)

Le NGOC améliore l'évaluation de l'alignement du réseau IPP pour l'ajustement biologique en prenant en compte le nombre total de protéines alignées.
Comme toutes les mesures d'évaluation biologique additionnant le score des nœuds alignés, un alignement peut être meilleur en cartographiant simplement plus de protéines que dans d'autres alignements.

### Aligner les réseaux IPP

L'objectif est de découvrir de grands sous-réseaux partagés entre les espèces et de dériver des relations phylogénétiques entre les espèces en examinant l'étendue du chevauchement présenté par les différents réseaux IPP. L'analyse comparative des réseaux de IPP entre les espèces permet d'identifier les sous-réseaux évolutifs conservés. Elle est souvent considérée comme un problème d'alignement des graphes où les protéines de différentes espèces sont superposées les unes aux autres sur la base des preuves accumulées de la grande similarité des séquences protéiques ainsi que de la grande similarité topologique.

#### Définition

Étant donné k réseaux IPP distincts $G_{1}=<P_{1},F_{1}>,G_{2}=<P_{2},F_{2}>,...,G_{k}=<P_{k},F_{k}>$ de k espèces différentes, le problème d'alignement des IPP est de trouver un sous-réseau conservé A, dans chacun des k graphes. Le graphe d'alignement A est un sous-graphe composé de nœuds représentant k protéines similaires (une par espèce), et d'arêtes représentant les interactions conservées entre les espèces. Chaque alignement Ai peut être représenté comme : $A_{i}=\{<p_{1i},p_{2i},...,p_{ki}>\}|p_{ji}\in P_{j}$
Le problème d'alignement recherche un ensemble optimal $A(G_{1},...,G_{k})=\{A\}_{i...k}$ alignements en maximisant la couverture des sommets de tous les réseaux participants.

#### Alignements par paires

Un alignement de réseau IPP par paire est un alignement limité à deux espèces seulement (k = 2). Étant donné deux réseaux, on trouve un alignement optimal des nœuds entre les deux. Le principal objectif de l'alignement de deux réseaux d'IPP de deux espèces est de trouver des protéines conservées chez les deux espèces. Avec deux ou plusieurs réseaux d'IPP, on peut effectuer deux types d'alignement : l'alignement global ou l'alignement local.
Dans l'alignement global, chaque nœud d'un réseau est aligné sur un seul nœud de l'autre réseau, ce qui produit une seule correspondance globale de deux ou plusieurs réseaux. Dans l'alignement global des réseaux, chaque nœud du plus petit réseau est aligné de manière unique sur un seul nœud du plus grand réseau qui correspondra le mieux. Un tel alignement permet de détecter un sous-réseau maximal, ce qui est utile pour la prédiction de l'orthologie fonctionnelle$^,$.
En revanche, l'alignement local tente de trouver le meilleur alignement des sous-réseaux d'un réseau avec les sous-réseaux d'un autre réseau, sans se soucier de la façon dont les autres nœuds s'alignent. Les méthodes d'alignement local peuvent produire des alignements de nœuds d’un à plusieurs, où un nœud d'un réseau peut être aligné sur plusieurs nœuds de l'autre réseau. Dans l'alignement local, les petites régions de similarité sont appariées indépendamment, et plusieurs de ces régions peuvent se chevaucher de manière conflictuelle. Sur le plan informatique, l'alignement local est moins coûteux que l'alignement global, car ce dernier vise à trouver une seule grande correspondance cohérente.

#### Alignements multiples

Si nous avons k réseaux IPP (avec k > 2), et que nous sommes chargés de trouver un alignement de tous les réseaux, le problème devient plus difficile. L'alignement de plusieurs réseaux IPP peut permettre de mieux comprendre les fonctions et les interactions des protéines, ce qui conduira à une meilleure compréhension de l'évolution des espèces. Même si les alignements de réseaux multiples ont été conçus et mis en œuvre pour traiter plus de deux réseaux d'entrée, ils peuvent toujours être utilisés comme des alignements par paires lorsque le nombre de réseaux IPP n'est que de deux.
Tableau 1- Comparaison de différentes techniques d’alignements IPP. :
| Alignement | Technique | Année | Alignement par pair | Alignement multiple | Approche topologique | Approche fonctionnelle |
| Alignement local | Graemlin | 2006 | ✓ | | ✓ | ✓ |
| Alignement local | Graemlin 2.0 | 2009 | | ✓ | ✓ | ✓ |
| Alignement local | NetworkBLAST | 2008 | ✓ | | ✓ | ✓ |
| Alignement local | NetAligner | 2012 | ✓ | | ✓ | |
| Alignement global | IsoRank | 2008 | | ✓ | ✓ | ✓ |
| Alignement global | IsoRankN | 2009 | | ✓ | ✓ | ✓ |
| Alignement global | GRAAL | 2009 | ✓ | | ✓ | ✓ |
| Alignement global | GHOST | 2012 | ✓ | | ✓ | |
| Alignement global | Optnetalign | 2015 | ✓ | | ✓ | ✓ |
| Alignement global | PROPER | 2016 | ✓ | | ✓ | ✓ |