Notes de mise en œuvre. Un algorithme de tri des permutations signées par inversions

Code


Pourquoi Applet
J’ai choisi d’implémenter cet outil en tant qu’applet car il permet un accès facile de n’importe qui de n’importe où à cet outil. Il s’agit de la première implémentation de cet algorithme (pour autant que je sache) et puisque cet algorithme est le plus rapide pour ce problème, je considère cet accès facile comme l’une des propriétés les plus importantes de cet outil. Les principaux inconvénients des applets (liés aux applications) sont les limitations de sécurité comme l’accès aux fichiers (pas d’accès aux fichiers) ou la validation des lignes de commande dos. Pour cette raison, j’ai ajouté le mode statistique afin de permettre une bonne estimation de la distance d’inversion d’une permutation en fonction de sa taille.

Pourquoi Java
L’implémentation était en Java et le code est disponible ici. Les principales raisons du choix de Java sont la mise en œuvre confortable de l’interface graphique et la simplicité de génération d’une applet. L’aspect le plus problématique de Java, l’efficacité, est devenu presque hors de propos par l’efficacité de l’algorithme et la taille (relativement) petite de l’entrée attendue (pas de données génomiques pures de millions ou de milliards de paires de bases mais de centaines ou de milliers de régions génomiques représentées comme une permutation signée). Le temps d’exécution de l’algorithme sur ces tailles d’entrée est mesuré en secondes (pour le mode rapide).
 

Classes d’interface utilisateur graphique

Ces cours ne sont pas très intéressants. Ils contiennent l’implémentation de l’interface graphique et sont grands et simples)

  • GR_applet.java – Cette classe contient l’implémentation de l’interface utilisateur pour l’utilisation de l’algorithme. Cette classe présente la fenêtre de dialogue principale et active les fonctionnalités de haut niveau de l’outil (choisissez un mode, choisissez une permutation, exécutez l’algorithme, etc.)
  • AnalysisFrame.java – Cette classe contient l’implémentation de la fonctionnalité « faible » de l’outil, c’est-à-dire l’analyse détaillée d’une permutation spécifique qui inclut une liste de différentes propriétés et un dessin du graphique des points d’arrêt.

Algorithme et ses classes auxiliaires

  • GR.java – une implémentation de haut niveau de l’algorithme de réarrangement du génome. La plupart de l’interaction entre les classes GUI et les classes d’algorithme se fait à travers cette classe. Cette classe « connaissance » est le flux principal de l’algorithme (comme franchir les obstacles ou trouver une clique heureuse). Il utilise la classe OVGraph pour exécuter l’algorithme.
  • OVGraph.java – La classe Overlap Graph. Il s’agit de la classe principale de l’algorithme (implémentation de bas niveau de l’algorithme). Cette classe fait la plupart du travail et possède des fonctionnalités très spécifiques. Cette classe n’est pas indépendante et elle ne peut être utilisée qu’avec sa « interface » – classe GR.
  • C_component.java – Un composant connecté dans le graphique de chevauchement
  • Permutation.java – une permutation
  • Reversal.java – une petite classe de retournement

Classes génériques

Pas dans les autres classes de groupe

  • Statistics.java – implémentation du mode statistique du programme (utilisé par GR_applet)

Développement futur

Temps différé
Comme je l’ai souligné précédemment, l’outil ne peut pas fonctionner en mode batch en raison des restrictions de sécurité que les applets ont (après tout, personne ne veut que quelque chose (une applet dans notre cas) qui existe dans une page Web qu’il a accidentellement chargée, exécuter la ligne de commande « del C: \ *. * » ou même lire des fichiers et les envoyer à son créateur). La façon de convertir cet outil en un outil en mode batch (qui, par exemple, lit 10 000 permutations signées dans un format spécifique et exécute l’algorithme sur chacune d’entre elles) n’est pas très compliquée. Il contient les étapes suivantes:

  1. Créez une classe de lecteur avec les méthodes suivantes: Reader (String filename) qui ouvre le fichier en lecture, Readline () qui lit la ligne à côté de celle qui a été lue lors du dernier appel et close () qui ferme le fichier. Le fichier peut être construit par un simple script dans n’importe quel langage de script.
  2. Comprendre l’interaction de la classe GR_applet avec la classe GR. Il s’agit de l’étape la plus importante de cette conversion. GR fournit une bonne interface et le code GR_applet utilise cette interface. Obtenir une séquence d’inversion est facile en construisant un objet GR et en invoquant GR :: run (). L’obtention des propriétés d’une permutation peut être effectuée par quelques méthodes simples de la classe Permutation. La plupart des méthodes disponibles sont utilisées dans la classe Statistics (avec GR :: getPermutation puis Permutation :: getBreakpointsNumber, Permutation :: getCyclesNumber, …) et il est recommandé de jeter un œil à cette section également.
  3. Écrivez une application Java qui obtient au moins un paramètre (le nom du fichier) et contient une boucle principale qui obtient une permutation (via le Reader) et la gère. Cette gestion contiendra généralement l’exécution de l’algorithme (avec GR :: run ()) et obtiendra les tableaux d’inversion ou l’analyse des propriétés du graphe de chevauchement (avec GR :: getPermutation puis Permutation :: getBreakpointsNumber, Permutation :: getCyclesNumber,. ..).

Développement futur
L’outil fournit toutes les fonctionnalités raisonnables auxquelles je pouvais penser. La plupart des améliorations possibles sont dans l’aspect GUI et certaines dans l’aspect efficacité.
Comme toujours lors de la construction d’un programme sans cibles spécifiques, la plupart des fonctionnalités de l’outil ont été ajoutées à la dernière étape de la programmation. Comme le bouclier du programme était bien formé (j’ai passé la plupart du temps à le construire et à l’améliorer), il est devenu assez facile d’améliorer la fonctionnalité en peu de temps, en particulier du côté de l’interface graphique. Malheureusement, je n’ai pas eu un temps illimité et malgré l’amélioration du projet devenu facile, le projet est entré dans sa phase de soumission, je n’ai apporté qu’une partie de l’amélioration possible à laquelle je pouvais penser.

Améliorations possibles:

– Interface utilisateur graphique

  • L’outil possède 2 fenêtres principales avec des fonctionnalités se chevauchant partiellement. Comme je le vois, la meilleure façon de mettre en œuvre l’outil est de diviser la fonctionnalité en 2 parties. La seconde contiendra toutes les fonctionnalités disponibles sur une permutation (y compris l’inversion utilisateur) et sera la dans le cadre d’analyse. Le premier contiendra le reste (c’est-à-dire la fonctionnalité jusqu’à ce qu’il y ait une permutation initiale) et sera dans l’applet. La raison pour laquelle je ne l’ai pas fait moi-même est que le cadre d’analyse a commencé comme un simple formulaire de texte de rapport et j’ai ensuite ajouté le dessin et les boutons. Quand j’ai trouvé qu’il était très confortable d’exécuter l’algorithme dans ce cadre, il était déjà trop tard pour le changer.
  • Permet à l’utilisateur de choisir une inversion en cliquant sur 2 sommets.
  • Affichez le graphique des points d’arrêt.

– Efficacité

  • Dans la version actuelle, le graphique est dessiné à partir de zéro à chaque changement. J’ai utilisé un mécanisme de double tampon afin d’éviter le scintillement, mais cela prend trop de temps, en particulier pour les gros graphiques. Il peut être amélioré en dessinant le « delta » (différence symétrique) au lieu de dessiner à partir de zéro. Le delta peut être atteint par une nouvelle méthode de l’objet OVGraph (meilleure mais plus compliquée) ou en comparant l’ancien graphique au nouveau (gérer uniquement les classes GUI mais moins efficace). Le second suffira probablement. Lorsque vous avez le delta, il est facile de « dessiner » des bords blancs pour effacer les bords et les bords colorés pour les nouveaux bords (et la couleur changée).
  • Il en va de même pour les menus locaux qui montrent les inversions légales que l’utilisateur peut effectuer. Dans la version actuelle, les menus sont vidés et remplis à partir de zéro. Il sera préférable que les menus soient mis à jour avec le delta des changements. Je ne suis pas sûr que ce soit possible dans tous les cas, mais au moins la réduction des éléments dans le menu sera plus rapide de cette façon.
  • J’ai utilisé un algorithme simple (DFS) pour diviser le graphique de chevauchement en composants connectés. Dans l’article de Berman et Hannenalli, il existe une description d’un sous-algorithme plus rapide pour ce problème. La mise en œuvre de ce sous-algorithme pourrait réduire la complexité du pire des cas de l’algorithme (de O(N^2) to O(N*a(N)+r*N) lorsque r est la distance d’inversion et a est la fonction Ackermann). D’après mon analyse du travail de l’algorithme, cette amélioration n’apportera pas une amélioration significative de l’efficacité attendue de l’outil car la plupart des permutations (vous pouvez le vérifier par le mode statistique) de taille N ont une distance d’inversion très proche de N. Comme il est très rare de trouver une permutation avec une distance d’inversion inférieure à N/2, la complexité ne devrait pas s’améliorer de manière significative.

Source de la page: http://www.math.tau.ac.il/~rshamir/GR/implementation.html
Traduit par Jean-Etienne Bergemer

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *