Tests unitaires

27 juillet 2009

Un programme informatique, tant qu’il ne fait qu’imprimer « Hello World! » à l’écran, ça a l’air tout bête. Mais dès qu’on essaie d’en faire un peu plus, ça devient plus délicat… Alors vous imaginez ce qu’il en est lorsqu’on développe un programme informatique totalisant des milliers de lignes de code ! Par exemple voir le cas de BLAST pour les languages C/C++ ou Biopython pour le language Python.

A cela s’ajoute une difficulté de taille: le code évolue, tout le temps. De ce point de vue, un programme informatique est très proche, conceptuellement parlant, d’un organisme vivant. Il manipule de l’information, remplit une fonction bien précise et doit être performant dans un environnement donné. Malheureusement, à chaque fois qu’un développeur (le type qui pianote sur son clavier toute la journée…) met son nez dans le code pour y ajouter ou modifier quelque chose, il risque de casser autre chose (une mutation délétère en quelque sorte), et la plupart du temps sans s’en rendre compte.

crash test

Dans ces conditions, soit vous êtes comme Donald Knuth et vous savez écrire un programme dans les règles de l’Art qui compile du premier coup, soit vous êtes comme tout le monde et vous testez votre code. Les informaticiens étant des gens très pointilleux, vous imaginez bien qu’ils ont peaufiné la chose: une bonne façon de développer est de le faire en Test-Driven Development (TDD).

Pour ce faire, supposons que l’on veuille impimer « METHINKS IT IS LIKE A WEASEL » à l’écran (lire cet article pour comprendre l’origine de la phrase…). Disons que l’on utilise la programmation orientée objet pour développer et qu’on écrit le code en TDD. Pratiquement, on aura une classe « Example » ayant un attribut « message » correspondant à la phrase donnée ci-dessus et ayant une méthode « getMessage() » qui servira à renvoyer le message en attribut.

En bon élève, on commence par écrire le test. Voici ce que ça donne en Python:

import unittest
import Example
class Test_Example( unittest.TestCase ):
    def test_getMessage( self ):
        expected = "METHINKS IT IS LIKE A WEASEL"
        myObject = Example.Example();
        observed = myObject.getMessage();
        self.assertEqual( observed, expected )
test_suite = unittest.TestSuite()
test_suite.addTest( unittest.makeSuite( Test_Example ) )
if __name__ == '__main__':
    unittest.TextTestRunner(verbosity=2).run( test_suite )

On exécute ce bout de code et bien sûr le test ne passe pas puisqu’on n’a pas encore écrit la classe à tester. Ce qu’on s’empresse de faire:

class Example:
    def __init__( self ):
        self.message = "METHINKS IT IS LIKE A WEASEL"
    def getMessage( self ):
        return self.message
if __name__ == '__main__':
    main()

On relance le code de test et maintenant ça passe: il renvoie « ok ». On sait donc que notre méthode « getMessage() » fait bien ce qu’on lui demande de faire.

$ python Test_Example.py
test_getMessage (__main__.Test_Example) ... ok
----------------------------------------------------------------------
Ran 1 test in 0.001s
OK

Vu comme ça, ce billet de blog paraît un peu léger, je m’en doute. Mais il faut savoir que cette approche très « professionnelle » de la programmation (ExtremeProgramming, méthodes Agiles) est bien souvent absente des labos de bioinformatique. Un chercheur peut alors se retrouver à télécharger le dernier programme publié dans Bioinformatics sans que celui-ci ne fonctionne (en gros, on installe, on lance et ça plante). Mais le pire arrive lorsque le programme téléchargé tourne sans bug apparent mais ne fait pas exactement ce que ses auteurs prétendent qu’il fasse…

Pour éviter ça et faire évoluer votre code de manière modulaire et adaptive, faites des tests unitaires ;-). Vous verrez, on s’y met très vite, d’autant plus que cette façon de travailler est grandement simplifiée grâce aux bibliothèques de tests unitaires déjà existantes: unittest en Python et cppunit en C++. En C++, c’est moins évident de comprendre du premier coup comment intégrer cppunit dans son code. Si vous voulez un exemple qui marche (on en trouve plein sur le web mais à qui il manque toujours qqch pour que ça compile comme il faut), demandez-moi, je peux vous en fournir un…

Publicités

Struggle for Life

15 juillet 2009

Le New York Times a eu une très bonne idée en mettant à disposition des internautes anglophiles une version de l’Origine des Espèces annotée par des professeurs de biologie évolutive.

Darwin cartoon

J’en profite pour mettre en lumière un exemple:

I should premise that I use the term Struggle for Existence in a large and metaphorical sense, including dependence of one being on another, and including (which is more important) not only the life of the individual, but success in leaving progeny.

Charles Darwin

Et voici le commentaire de Frans de Waal:

A Struggle Not Limited to Physical Combat: What I like about this particular quote is how Darwin was averse to the simplifications of many contemporary popularizers of evolutionary biology. One often hears that nature is where the strong survive, and that might is right, so that those who are too weak to do well not only may perish, but in fact ought to perish. Darwin didn’t endorse any such views, and didn’t see nature as the gladiator’s show that his public defender, Thomas Henry Huxley, projected onto it. For him, the term « struggle » was not limited to physical combat. Darwin considered it possible that some animals survive through cooperation, depending on one another, and that others survive simply by being better at finding food, fighting off diseases, or withstanding the cold or dryness of their climate. Fitness in a given environment may mean having a thick fat layer, or possessing sharp eyes. Physical strength is only one out of thousands of traits that determine which individuals will do well.This contains a profound lesson for those who wish to apply Darwinism to society around us, going so far as calling Wall Street a “Darwinian jungle.” Wall Street hasn’t done too well with its simplistic dog-eat-dog view, and should pay more attention to true evolutionary theory, which stresses adaptability to change rather than direct competition.

Frans B. M. de Waal

Je me permets de traduire ce qui est en gras ci-dessus: « Pour lui [Darwin], le terme « struggle » ne se limitait pas au combat physique. Darwin considérait qu’il était possible que certains animaux survivent grâce à de la coopération, dépendant les uns des autres, et que d’autres survivent simplement parce qu’ils étaient meilleur dans la recherche de nourriture, dans la résistance aux maladies ou l’endurance du froid et de la sécheresse du climat ».

En ces temps de Darwinomania, il est bon de revenir aux sources: lire le bouquin !


Significativité d’un alignement pour BLAST

12 juillet 2009

On a vu il y a quelque temps comment estimer la significativité d’un alignement en utilisant la formule de Bayes. Mais pratiquement, ce n’est pas la méthode la plus utilisée. Il est temps d’introduire BLAST…

Derrière cet acronyme percutant se cache l’algorithme le plus utilisé en alignement de séquences biologiques. Il correspond à une heuristique d’alignement local deux-à-deux présenté dans l’article « Basic local alignment search tool » dont il tire son nom. Cet article d’Altschul, Gish, Miller, Myers et Lipman, paru en 1990, a fait date: à ce jour il a été cité dans au moins 30000 publications, un record! Il est très utilisé parce qu’il est rapide et permet de trouver les alignements significatifs entre une sequence inconnue et une (très) grande banque de séquences connues.

Cet algorithme fonctionne en plusieurs étapes. Étant donné deux séquences à comparer, il commence par rechercher des segments de longueur égale, sans gap,  identiques entre eux. On appelle ça les seeds, ce sont des k-mers avec k=11 pour des séquences nucléotidiques. Puis l’algorithme essaie d’étendre ces seeds en autorisant les gaps: il obtient alors des HSPs (pour high-scoring segment pairs). Finalement, pour chaque HSP (donc pour chaque alignement local entre les deux séquences),  l’algorithme choisit ceux dont le score est considéré comme étant significatif.

Optimisation of the Smith-Waterman algorithm

Supposons que l’on aligne une séquence de fonction inconnue, la query, de taille m, avec une séquence de fonction connue, la subject, de taille n, via BLAST. On obtient N HSPs, chacun ayant un score H. Pour estimer la significativité d’un HSP, on a besoin de savoir à quel point c’est probable d’obtenir un HSP de score H par hasard, sans que les deux séquences aient quoi que ce soit à voir entre elles. Cela revient à calculer la probabilité que le score maximal des N HSPs obtenus dépasse un seuil S donné.

Maintenant considérons que les H_i sont des variables aléatoires indépendamment distribuées selon une densité de probabilité f(H).  Si on prend leur maximum X = \max_i ( H_i ), on peut écrire:

P_N ( X \le S ) = P(H_1 \le S) ... P(H_N \le S)

P_N ( X \le S ) = \left( \int_{-\infty}^{S} p(H) \, dH \right)^N

P_N ( X \le S ) = \left( 1 - \int_{S}^{+\infty} p(H) \, dH \right)^N

Si les deux séquences ont beaucoup d’HSPs entre elles (N grand) et comme S est vraisemblablement élevé, il est dans la queue de la distribution et donc la surface sous l’intégrale est petite. On peut donc appliquer l’approximation bien connue (1-x)^k \approx \exp^{-kx} quand x est petit:

P_N ( X \le S ) \approx \exp \left( - N \int_{S}^{+\infty} p(H) \, dH \right)

Maintenant, supposons pour l’instant que p(H) tombe exponentiellement sur ces extrêmes (les queues de distribution, quand S est suffisamment grand):

\int_{S}^{+\infty} p(H) dH = \int_{S}^{+\infty} a \exp^{-\lambda H} dH = \frac{a}{\lambda} \exp^{-\lambda S}

Ainsi: P_N ( X \le S ) \approx \exp \left( - \frac{Na}{\lambda} \exp^{-\lambda S} \right)

Finalement, la probabilité que le score maximal X des N HSPs obtenus entre nos deux séquences dépasse un seuil S donné vaut:

P_N ( X > S ) \approx 1 - \exp \left( - \frac{Na}{\lambda} \exp^{-\lambda S} \right)

Cette formule nous permet donc de dire quand le score X tombe dans les 1% ou 5% de la distribution. C’est bien ce qu’on cherchait, non ?

Pour la petite histoire, X suit une distribution dite « des valeurs extrêmes ». Vous pouvez trouver ici l’article de Gumbel, en français, décrivant les premiers résultats. On se sert de cette théorie dans de nombreux domaines, notamment en finance et assurance, pour estimer la variabilité d’un système et donc les risques d’atteindre des valeurs extrêmes. Les lois des valeurs extrêmes ont l’une de leur queues de distribution plus épaisse que la loi normale, donc la probabilité d’occurrence d’une valeur extrême, c’est-à-dire tombant dans cette queue de distribution plus épaisse, est plus forte que pour une loi normale. Mais certains aiment quand même bien la loi normale, et un prix Nobel ça inspire confiance, quoique après ça, certains vont réviser leur modèles…

Loi Normale et loi de GumbelLa 1e image est tirée de « The estimation of statistical parameters for local alignment score distribution », Althschul et al., Nucleic Acids Research, 2001. Quant à la 2e image, voici le code R pour la générer:


require( distrEx )
require( Cairo )
Cairo( "normal_vs_gumbel.png", width=700, height=500, bg="white" )
x <- seq(-4,6,0.01)
par( mar=c(5,5,3,2), font=2, font.axis=2, font.lab=2, cex=1.5, lwd=2 )
plot( x, dnorm(x), type="l", col="black", main="Loi Normale et loi de Gumbel", ylab="densité de probabilité", ylim=c(0.0,0.5), xlim=c(-4,6) )
points( x, dgumbel(x), type="l", col="red" )
abline( v=0, lty=2, lwd=1 )
legend( 0.2, 0.5, c( "densité de la loi Normale", "densité de la loi de Gumbel" ), col=c("black","red"), lwd=2, bty="n" )
dev.off()

Ajout: un tutoriel sur BLAST vient de sortir dans PLoS Biology, avec une figure qui résume très bien les différentes étapes.


Nuit noire, ciel étoilé ?

9 juillet 2009

Les yeux fatigués, le cerveau embrumé, je dépile mes mails après quelques jours sans internet… mais il suffit d’un billet pour exciter les quelques neurones qui s’agitent encore dans un coin: on m’envoie un extrait d’un discours de François Jacob devant l’Académie des Science, discours à propos du courage, mais l’extrait qui nous intéresse ici concerne ce que François Jacob dénomme la science de nuit par opposition à la science de jour, le voici:

La science a en fait deux aspects. Ce qu’on pourrait appeler science de jour et science de nuit. La science de jour met en jeu des raisonnements qui s’articulent comme des engrenages, des résultats qui ont la force de la certitude. On en admire la majestueuse ordonnance comme celle d’un tableau de Vinci ou d’une fugue de Bach. On s’y promène comme dans un jardin à la française. Consciente de sa démarche, fière de son passé, sûre de son avenir, la science de jour avance dans la lumière et la gloire.

ciel étoilé

La science de nuit, au contraire, erre à l’aveugle. Elle hésite, trébuche, recule, transpire, se réveille en sursaut. Doutant de tout, elle se cherche, s’interroge, se reprend sans cesse. C’est une sorte d’atelier du possible où s’élabore ce qui deviendra le matériau de la science. Où les hypothèses restent sous forme de pressentiments vagues, de sensations brumeuses. Où les phénomènes ne sont encore qu’évènements solitaires sans lien entre eux. Où les projets d’expériences ont à peine pris corps. Où la pensée chemine à travers des voies sinueuses, des ruelles tortueuses, le plus souvent sans issue. À la merci du hasard, l’esprit chemine dans un labyrinthe, sous un déluge de messages, en quête d’un signe, d’un clin d’œil, d’un rapprochement imprévu. Comme un prisonnier dans sa cellule, il tourne en rond, cherche une issue, une lueur. Sans s’arrêter, il passe de l’espoir à la déconvenue, de l’exaltation à la mélancolie. Rien ne permet de dire que la science de nuit passera jamais au stade de science de jour. Que le prisonnier sortira de l’ombre. Si cela survient, c’est de manière fortuite, comme un caprice. À l’improviste, comme une génération spontanée. N’importe où, n’importe quand, comme la foudre. Ce qui guide l’esprit alors, ce n’est pas la logique. C’est l’instinct, l’intuition. C’est le besoin d’y voir clair. C’est l’acharnement à vivre. C’est le courage. Dans l’interminable dialogue intérieur, parmi les innombrables suppositions, rapprochements, combinaisons, associations qui sans cesse traversent l’esprit, un trait de feu parfois déchire l’obscurité. Éclaire soudain le paysage d’une lumière aveuglante, terrifiante, plus forte que mille soleils. Après le premier choc commence un dur combat avec les habitudes de pensée. Un conflit avec l’univers de concepts qui règle nos raisonnements. Rien encore n’autorise à dire si l’hypothèse nouvelle dépassera sa forme première d’ébauche grossière pour s’affiner, se perfectionner. Si elle soutiendra l’épreuve de la logique. Si elle sera admise dans la science de jour.

Ce que François Jacob décrit là, ce sont des moments que chacun, quel qu’il soit, a connu, connaît ou connaîtra sûrement. C’est aussi ce qui forme la toile de fond du travail du chercheur, dans son acceptation la plus basique: celui qui cherche, qui tâtonne, mais qui persévère. Et je trouve que François Jacob l’exprime ici de manière à la fois sincère et rêveuse. Cela rappelle ce tressaillement que l’on peut avoir lorsque l’on sent confusément qu’une intuition est juste, ce mystérieux enchainement de causes et conséquences, mêlant observation, réfléxion, mémoire et imagination, qui soudain prend forme, cet enchaînement que l’on aimerait pouvoir comprendre suffisamment afin de pouvoir le susciter « à volonté », ou tout le moins que l’on aimerait pouvoir transmettre. D’ailleurs, ne serait-ce pas cela le but de l’éducation: transmettre le désir de connaître l’étincelle créatrice ?


%d blogueurs aiment cette page :