Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Sources
Pour le cours d’Algorithmique de la bioinformatique (BNF 103)
(liens et références utiles)
Article mis en ligne le 12 février 2007
dernière modification le 8 mars 2010

par Laurent Bloch

Le cours d’Algorithmique de la bioinformatique (BNF 103) vient à la suite du cours BNF 102 d’initiation à la programmation. Il consiste en la présentation de méthodes et d’algorithmes, que les auditeurs devront ensuite programmer pendant les Enseignements dirigés et leur travail personnel. Vous pouvez consulter le plan du cours, qui donne aussi la table des matières des articles dans l’ordre des séances de cours.

Vous trouverez dans la présente rubrique des informations, des documents et des liens relatifs à l’enseignement. Il est également conseillé de consulter le site de la chaire de Bioinformatique.

Ce cours a été dispensé en 2005 par William Saurin, qui ne peut l’assurer cette année, et qui m’a transmis ses notes. Je suivrai la même démarche que lui en m’inspirant des documents qu’il m’a communiqués, et dont vous retrouverez une partie ici-même.

Ainsi qu’il a été mentionné ci-dessus, les participants à ce cours devront écrire les programmes qui correspondent aux algorithmes étudiés : il serait possible d’écrire à son fronton (virtuel) « Que nul n’entre ici s’il n’est programmeur » . Le langage de programmation utilisé sera Scheme, pour lequel vous trouverez ici des références, tant pour la bibliographie que pour les logiciels libres dont vous aurez besoin.

Documents en ligne, ici ou ailleurs

Pour ce cours, vous trouverez sur ce même site des informations utiles dans d’autres rubriques :

 tout d’abord, un document qui récapitule des liens vers tout de dont vous aurez besoin pour démarrer la programmation en Scheme, et de façon plus générale la
rubrique consacrée à Scheme ;
 et la compilation des compléments de cours et corrigés d’exercices de BNF 102.

Sur le site de l’Institut Pasteur, un cours de Katja Schürer donne une Introduction to Algorithmics for Biologists très approfondie.

Voici en ligne sur le site d’un des auteurs un excellent cours d’algorithmique, très complet et exempt de mathématiques superflues, par Robert Cori et Jean-Jacques Lévy.

Voir aussi la bibliographie ci-dessous.

Bibliographie

Voici quelques références bibliographiques pour l’algorithmique :

Cormen (Thomas), Leiserson (Charles), Rivest (Ronald) et Stein (Clifford), 1994-2002, Introduction à l’algorithmique , Paris, Dunod (pour la traduction française de Xavier Cazin et Georges-Louis Kocher), 1146 pages.
Une somme d’une complétude impressionnante ; si les exposés mathématiques des algorithmes sont d’une grande clarté, le passage à la programmation (en pseudo-code) est souvent difficile.

Gusfield (Dan), 1997, Algorithms on Strings, Trees, and Sequences — Computer Science and Computational Biology , Cambridge, Cambridge University Press, 534 pages.
Ce livre offre une présentation très large de ce que l’on appelle l’algorithmique sur les mots ou les chaînes de caractères telles les séquences biologiques. Y sont ainsi présentés les algorithmes « classiques » sur les chaînes, ainsi que les développements nouveaux inspirés par des problèmes divers en biologie moléculaire (comparaison de séquences, extraction de motifs, recherche de répétitions et de palindromes, phylogénie, cartographie, assemblage entre autres). En ce qui concerne l’algorithmique classique, une grande importance est accordée à l’utilisation d’une structure particulière qui est celle des arbres de suffixes.

Maxime Crochemore, Christophe Hancart et Thierry Lecroq, 2001, Algorithmique du texte , Vuibert, 347 pages, avec un site de compléments.
Il s’agit du premier ouvrage en Français d’algorithmique spécialisée sur le traitement du texte. Il suppose une connaissance de base des méthodes de conception de programmes et d’évaluation de leurs performances. Il peut être utilisé dans un cours d’algorithmique classique. Chaque chapitre est assorti des références bibliographiques principales et d’une liste d’exercices. Il présente les bases techniques utilisées dans les domaines de la recherche documentaire, de l’indexation pour les moteurs de recherche et des logiciels systèmes. Les méthodes qui sont décrites trouvent leurs applications dans les questions de traitement de la langue naturelle, d’analyse des séquences génétiques et de bases de données textuelles.

J.E. Hopcroft et Jeffrey D. Ullman, 1979-2006, Introduction to Automata Theory, Languages and Computation , Addison et Wesley, 428 à 535 pages selon l’édition (la première est plus abordable d’occasion et n’a pas pris une ride). Cet ouvrage introduit de façon lumineuse les automates à états finis, les langages réguliers et bien d’autres choses, qui du coup apparaissent fort simples.

Olivier Cogis et Claudine Robert, 2003, Au-delà des ponts de Königsberg : Théorie des graphes , Vuibert, 252 pages. Comme il vous faudra savoir au moins ce qu’est un arbre, ce livre donne une excellente introduction au sujet, avec aussi peu de formalismes mathématiques que possible, et c’est d’une lecture très agréable.