La classification des gènes basée sur les CSP pondérés
| Autor: | Ben Mhenni, Ramzi, MHAMDI, Amel, Naanaa, Wady |
|---|---|
| Přispěvatelé: | BEN MHENNI, RAMZI, Faculté des Sciences de Monastir (FSM), Université de Monastir - University of Monastir (UM), Faculté des Sciences Economiques et de Gestion de Sfax (FSEG Sfax), Université de Sfax - University of Sfax |
| Jazyk: | francouzština |
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Actes des Douzièmes Journées Francophones de Programmation par Contraintes JFPC 2016 Douzièmes Journées Francophones de Programmation par Contraintes JFPC 2016 Douzièmes Journées Francophones de Programmation par Contraintes, Jan 2016, Montpellier, France |
| Popis: | The classification of objects relative to a similarity or a given distance is a central problem in computational biology. Several well-known classification algorithms, such as partitioning problem of similar genes, are based on the transformation of the input matrix into a weighted graph, although the resulting weighted cluster editing problem is NP-hard. The goal is to transform the input graph into a union of disjoint cliques such as the sum of the weights of all modified edges is minimized. In this article, we propose an encoding of the classification of similar genes in terms of a Weighted Constraint Satisfaction Problem (WCSP), which we solve by an adapted version of an efficient constraint solver. We compare both quality and running times of these algorithms on protein similarity graphs. A comparison of our method with an exact fixed-parameter tractability method and an integer linear programming algorithm, two of the most used algorithms, shows that our approach is able to solve large instances with several thousand edge modifications. La classification des objets par rapportàrapportà une similitude ou une distance donnée est unprobì eme souvent rencontré dans desprobì emes de bio-informatique. Plusieurs algorithmes de classification bien connus, tel que les algorithmes de partitionnement des gènes similaires, sont basés sur la transformation de la matrice d'entrée vers un graphe pondéré bien que leprobì eme d'édition de graphe pondéré résultant est NP-difficile. Le but est de transformer le graphe en entrée en une union de cliques disjointes telles que la somme des poids de toutes les arêtes modifiées soit minimisée. Dans cet article, Nous présentons une nouvelle ap-proche pour leprobì eme de classification des gènes en terme deprobì eme de satisfaction de contrainte pondéré (WCSP). Uné etude comparative avec les deux approches les plus utilisées pour la résolution duprobì eme de classification des gènes similaires, qui sont les algorithmesàalgorithmesà paramètre fixe et les algorithmes s'appuyant sur la pro-grammation linéaire en nombre entier, sera proposée. Nous montrons que l'approche proposée permet souvent de trouver une solution optimale en temps raisonnable. Nous avons appliqué notre algorithmè a des données bio-logiques. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|