Accès à l'intranet
Français
Efficient algorithms for partial alignment
Document Actions
Elligible students to INRIA internship have to apply through this program but questions about the subject can be sent directly to fcoste@irisa.fr.
Subject: In the context of learning automata for modeling biological sequences
[1], we introduced in the Symbiose project a new kind of sequence
alignment named partial local multiple sequence alignment.
The partial alignment problem can be formalized as a search of an
optimal k-matching under constraints [2] but, until now, the partial
alignments are built by heuristic greedy procedures. The goal of this
subject is to propose and implement new algorithms allowing to build
efficiently better alignments.
Keywords: Optimization, constraint satisfaction, linear programming, clique, connected components.
Prerequisites: Strong programming, operational research, optimisation or linear programming skills
Duration: 5-6 months
Bibliography:
[1] Learning Automata on Protein Sequences, F. Coste and G. Kerbellec, JOBIM 2006
[2] Alignements Multiples de Séquences Protéiques, Y.P. Denielou, rapport de stage, juin 2006