Home About us Products Services Contact us Bookmark
:: wikimiki.org ::
Algorithme Génétique

Algorithme génétique

Les algorithmes génétiques (parfois appelés algorithmes évolutionnaires) appartiennent à une famille d'algorithmes appelés métaheuristiques dont le but est d'obtenir une solution approchée, en un temps correct, à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte pour le résoudre. Les algorithmes génétiques utilisent la notion de sélection naturelle développée au par le scientifique Darwin et l'appliquent à une population de solutions potentielles au problème donné.

Les origines

L'utilisation, dans la résolution de problèmes, d'algorithmes génétiques est à l'origine le fruit des recherches de John Holland et de ses collègues et élèves de l'Université du Michigan qui ont, dès 1960, travaillé sur ce sujet. La nouveauté introduite par ce groupe de chercheurs a été la prise en compte de l'opérateur de crossing over en complément des mutations. Et c'est cet opérateur qui permet le plus souvent de se rapprocher de l'optimum d'une fonction en combinant les gènes contenus dans les différents individus de la population. Le premier aboutissement de ces recherches a été la publication en 1975 de Adaptation in Natural and Artificial System.

Présentation

Analogie avec la biologie

Terminologie commune aux deux disciplines

Les algorithmes génétiques étant basés sur des phénomènes biologiques, il convient de rappeler au préalable quelques termes de génétique. Les organismes vivants sont tout d'abord constitués de cellules comportant des chromosomes qui correspondent en fait à des chaînes d'ADN. L'élément de base de ces chromosomes (le caractère de la chaîne d'ADN) est un gène. Sur chacun de ces chromosomes, une suite de gènes constitue une chaîne qui code les fonctionnalités de l'organisme (la couleur des yeux ...). La position d'un gène sur le chromosome est son locus. L'ensemble des chromosomes correspond au génome de l'individu. Les différentes versions d'un même gène sont appelées allèles. On utilise aussi, dans les algorithmes génétiques, une analogie avec la biologie, qui concerne l'évolution, hypothèse émise par Darwin et qui propose qu'au fil du temps, les gènes conservés au sein d'une population donnée sont ceux qui sont le plus adaptés aux besoins de l'espèce et à son environnement.

Les outils issus de la biologie

La génétique a mis en évidence l'existence de plusieurs opérations au sein d'un organisme donnant lieu au brassage génétique. Ces opérations interviennent lors de la phase de reproduction lorsque les chromosomes de deux organismes fusionnent. Ces opérations sont imitées par les algorithmes génétiques afin de faire évoluer les populations de solutions de manière progressive.
- Les sélections ::Pour déterminer quels individus sont plus enclins à obtenir les meilleurs résultats, une sélection est opérée. Ce processus est analogue à un processus de sélection naturelle, les individus les plus adaptés gagnent la compétition de la reproduction tandis que les moins adaptés meurent avant la reproduction, ce qui améliore globalement l'adaptation.
- Les crossing over ou recombinaison ::Lors de cette opération, deux chromosomes s'échangent des parties de leurs chaînes, pour donner de nouveaux chromosomes. Ces crossing-over peuvent être simples ou multiples. ::Dans le premier cas, les deux chromosomes se croisent et s'échangent des portions d'ADN en un seul point. Dans le deuxième cas, il y a plusieurs points de croisement. Pour les algorithmes génétiques, c'est cette opération (le plus souvent sous sa forme simple) qui est prépondérante. Sa probabilité d'apparition lors d'un croisement entre deux chromosomes est un paramètre de l'algorithme génétique. En règle générale, on fixe la proportion d'apparition à 0,7.
- Les mutations ::De façon aléatoire, un gène peut, au sein d'un chromosome être substitué à un autre. De la même manière que pour les crossing-over, on définit ici un taux de mutation lors des changements de population qui est généralement compris entre 0,001 et 0,01. Il est nécessaire de choisir pour ce taux une valeur relativement faible de manière à ne pas tomber dans une recherche aléatoire et conserver le principe de sélection et d'évolution. La mutation sert à éviter une convergence prématurée de l'algorithme. Par exemple lors d'une recherche d'extremum la mutation sert à éviter la convergence vers un extremum local

Principe

Les algorithmes génétiques, afin de permettre la résolution de problèmes, se basent sur les différents principes décrits ci-dessus. De manière globale, on commence avec une population de base qui se compose le plus souvent de chaînes de caractères correspondant chacune à un chromosome. Nous reviendrons par la suite sur les différentes structures de données possibles (voir Codage) mais nous retiendrons pour le moment l'utilisation du codage binaire (ex. : 0100110). Le contenu de cette population initiale est généré aléatoirement. On attribue à chacune des solutions une note qui correspond à son adaptation au problème. Ensuite, on effectue une sélection au sein de cette population. Il existe plusieurs techniques de sélection. Voici les principales utilisées :
- Sélection par rang :: Cette technique de sélection choisit toujours les individus possédant les meilleurs scores d'adaptation, le hasard n'entre donc pas dans ce mode de sélection.
- Probabilité de sélection proportionnelle à l'adaptation (appelé aussi roulette ou roue de la fortune) ::Pour chaque individu, la probabilité d'être sélectionné est proportionnelle à son adaptation au problème. Afin de sélectionner un individu, on utilise le principe de la roue de la fortune biaisée. Cette roue est une roue de la fortune classique sur laquelle chaque individu est représenté par une portion proportionnelle à son adaptation. On effectue ensuite un tirage au sort homogène sur cette roue.
- Sélection par tournoi :: Cette technique utilise la sélection proportionnelle sur des paires d'individus, puis choisit pour ces paires l'individu qui a le meilleur score d'adaptation.
- Sélection uniforme :: La sélection se fait aléatoirement, uniformément et sans intervention de la valeur d'adaptation. Chaque individu a donc une probabilité 1/P d'être sélectionné, où P est le nombre total d'individus dans la population.
- ... Lorsque deux chromosomes ont été sélectionnés, on réalise un crossing-over. On effectue ensuite des mutations sur une faible proportion d'individus, choisis aléatoirement. Ce processus nous fournit une nouvelle population. On réitère le processus un grand nombre de fois de manière à imiter le principe d'évolution, qui ne prend son sens que sur un nombre important de générations. On peut arrêter le processus au bout d'un nombre arbitraire de générations ou lorsque qu'une solution possède une note suffisamment satisfaisante. Considérons par exemple les deux individus suivants dans une population où chaque individu correspond à une chaîne de 8 bits : A = 00110010 et B = 01010100. On ajuste la probabilité du crossing over à 0.7. Supposons ici que le crossing-over ait lieu, on choisit alors aléatoirement la place de ce crossing-over (toutes les places ayant la même probablité d'être choisies). En supposant que le crossing-over ait lieu après le deuxième allèle, on obtient A' et B' (« : » marquant le crossing over sur A et B). Ensuite, chacun des gènes des fils (ici, chacun des bits des chaînes) est sujet à la mutation. De la même manière que pour les combinaisons, on définit un taux de mutation (très bas, de l'ordre de 0,001 - ici on peut s'attendre à ce que A' et B' restent identiques). En effectuant ces opérations (sélection de deux individus, crossing-over, mutation), un nombre de fois correspondant à la taille de la population divisée par deux, on se retrouve alors avec une nouvelle population (la première génération) ayant la même taille que la population initiale, et qui contient globalement des solutions plus proches de l'optimum. Le principe des algorithmes génétiques est d'effectuer ces opérations un maximum de fois de façon à augmenter la justesse du résultat. Il existe plusieurs techniques qui permettent éventuellement d'optimiser ces algorithmes, on trouve par exemple des techniques dans lesquelles on insère à chaque génération quelques individus non issus de la descendance de la génération précédente mais générés aléatoirement. Ainsi, on peut espérer éviter une convergence vers un optimum local.

Codage d'un algorithme génétique

Pour les algorithmes génétiques, un des facteurs les plus importants, si ce n'est le plus important, est la façon dont sont codées les solutions (ce que l'on a nommé ici les chromosomes), c'est-à-dire les structures de données qui coderont les gènes.

Codage binaire

Ce type de codage est certainement le plus utilisé car il présente plusieurs avantages. Son principe est de coder la solution selon une chaîne de bits (qui peuvent prendre les valeurs 0 ou 1). Les raisons pour lesquelles ce type de codage est le plus utilisé sont tout d'abord historiques. En effet, lors des premiers travaux de Holland, les théories ont été élaborées en se basant sur ce type de codage. Et même si la plupart de ces théories peuvent être étendues à des données autres que des chaînes de bits, elles n'ont pas été autant étudiées dans ces contextes. Cependant, l'avantage de ce type de codage sur ses concurrents a tendance à être remis en question par les chercheurs actuels qui estiment que les démonstrations d'Holland sur les avantages supposés de ce codage ne sont pas révélatrices. La démonstration d'Holland (en 1975) pour prouver la supériorité de ce type de codage est la suivante. Il compara deux types de codage pour le même problème. Le premier était composé de peu de types d'allèles mais avec des chromosomes d'une longueur importante (des chaînes de 100 bits par exemple), l'autre était composé de chaînes plus courtes mais contenant plus d'allèles (en sachant que tout autre codage, pour le même chromosome, aboutira à une chaîne plus courte). Il prouva que le codage sous forme de bits était plus efficace de manière assez simple. En effet, les chaînes de 100 bits permettent d'avoir plus de possibilités de crossing-over. Entre deux chromosomes du premier type, le crossing-over peut avoir lieu à 100 endroits différents contre 30 pour ceux du second type. Le brassage génétique sur lequel repose l'efficacité des algorithmes génétiques sera donc plus important dans le premier cas. Il existe cependant au moins un coté négatif à ce type de codage qui fait que d'autres existent. En effet, ce codage est souvent peu naturel par rapport à un problème donné (l'évolution des poids d'arcs dans un graphe par exemple est difficile à coder sous la forme d'une chaîne de bits).

Codage à caractères multiples

Une autre manière de coder les chromosomes d'un algorithme génétique est donc le codage à l'aide de caractères multiples (par opposition aux bits). Souvent, ce type de codage est plus naturel que celui énoncé ci-avant. C'est d'ailleurs celui-ci qui est utilisé dans de nombreux cas poussés d'algorithmes génétiques que nous présenterons par la suite.

Codage sous forme d'arbre

Ce codage utilise une structure arborescente avec une racine de laquelle peuvent être issus un ou plusieurs fils. Un de leurs avantages est qu'ils peuvent être utilisés dans le cas de problèmes où les solutions n'ont pas une taille finie. En principe, des arbres de taille quelconque peuvent être formés par le biais de crossing-over et de mutations. Le problème de ce type de codage est que les arbres résultants sont souvent difficiles à analyser et que l'on peut se retrouver avec des arbres « solutions » dont la taille sera importante alors qu'il existe des solutions plus simples et plus structurées à côté desquelles sera passé l'algorithme. De plus, les performances de ce type de codage par rapport à des codages en chaînes n'ont pas encore été comparées ou très peu. En effet, ce type d'expérience ne fait que commencer et les informations sont trop faibles pour se prononcer. Finalement, le choix du type de codage ne peut pas être effectué de manière sûre dans l'état actuel des connaissances. Selon les chercheurs dans ce domaine, la méthode actuelle à appliquer dans le choix du codage consiste à choisir celui qui semble le plus naturel en fonction du problème à traiter et développer ensuite l'algorithme de traitement.

Cas d'utilisation

Les conditions du problème

Comme cela a été dit plus haut, les algorithmes génétiques peuvent être une bonne solution pour résoudre un problème. Néanmoins, leur utilisation doit être conditionnée par certaines caractéristiques du problème. Les caractéristiques à prendre en compte sont les suivantes :
- Nombre de solutions important : En effet, les performances des algorithmes génétiques par rapport aux algorithmes classiques sont plus marquées lorsque les espaces de recherches sont importants. En effet, pour un espace dont la taille est faible, il peut être plus sûr de parcourir cet espace de manière exhaustive afin d'obtenir la solution optimale en un temps qui restera somme toute correct. Au contraire, utiliser un algorithme génétique engendrera le risque d'obtenir une solution non optimale (voir Limites) en un temps qui restera sensiblement identique.
- Pas d'algorithme déterministe adapté et raisonnable.
- Lorsque l'on préfère avoir une solution relativement bonne rapidement plutôt qu'avoir la solution optimale en une durée indéfinie. C'est ainsi que les algorithmes génétiques sont utilisés pour la programmation de machines qui doivent être très réactives aux conditions environnantes.

Exemples d'applications

Applications dans la recherche

Le problème du voyageur de commerce : Ce problème est un classique d'algorithmique. Son sujet concerne les trajets d'un voyageur de commerce. Celui-ci dispose de plusieurs points où s'arrêter et le but de l'algorithme est d'optimiser le trajet de façon à ce que celui-ci soit le plus court possible. Dans le cas où huit points d'arrêts existent, cela est encore possible par énumération (2520 possibilités [pour n arrêts,n supérieur ou égal à 3, il y a (n-1)!/2 chemins possibles) mais ensuite, l'augmentation du nombre d'arrêts fait suivre au nombre de possibilités une croissance exponentielle. Par le biais d'algorithmes génétiques, il est possible de trouver des chemins relativement corrects. De plus, ce type de problèmes est assez facile à coder sous forme d'algorithme génétique. L'idée de base est de prendre comme fonction d'adaptation d'un chemin sa longueur puis, pour effectuer le croisement de deux chemins, une fois que le locus où doit avoir lieu le crossing-over est sélectionné, on garde les itinéraires des deux chemins jusqu'à ce locus et on place dans le chemin A les villes qui ne sont pas présentes dans la première partie, dans l'ordre où elles apparaissent dans le chemin B. On fait le contraire pour le chemin B. Soit un itinéraire qui contient 9 clients, supposons que l'on croise les deux chemins suivants (un chiffre représente un client). Si l'on croise ces deux chemins après le locus 4, on obtient les deux chemins A' et B'. En partant de ce principe, de nombreux algorithmes génétiques ont été développés, chacun utilisant différentes variantes afin de se rapprocher le plus possible du maximum dans tous les cas. Il existe d'ailleurs un concours sur internet qui propose de développer un algorithme à même de trouver le meilleur chemin sur un problème de voyageur de commerce de 250 villes.

Applications industrielles

Un premier exemple est une réalisation effectuée au sein de l'entreprise Motorola. Le problème pour lequel Motorola a utilisé les algorithmes génétiques concerne les tests des applications informatiques. En effet, lors de chaque changement apporté à une application, il convient de retester l'application afin de voir si les modifications apportées n'ont pas eu d'influence négative sur le reste de l'application. Pour cela, la méthode classique est de définir manuellement des plans de test permettant un passage dans toutes les fonctions de l'application. Mais ce type de test nécessite un important travail humain. Le but de Motorola a donc été d'automatiser cette phase de définition de plans de tests. Ils ont pour cela défini un algorithme où chaque individu correspond à un résultat d'exécution d'un programme (l'enchaînement des valeurs passées au programme) et où chaque individu reçoit une valeur qui correspond à son aptitude à passer dans un maximum de parties du code de l'application. Finalement, l'outil développé permet, à l'aide d'un algorithme génétique, de faire évoluer ces programmes de test pour maximiser les zones testées de façon à ce que lors de modifications apportées à l'application on puisse soumettre celle-ci à des tests efficaces. D'autres domaines industriels utilisent aujourd'hui les algorithmes génétiques. On peut retenir entre autres l'aérodynamique où des optimisations sont mises au point à l'aide de ces outils, l'optimisation structurelle, qui consiste à minimiser le poids d'une structure en tenant compte des contraintes de tension admissibles pour les différents éléments, et la recherche d'itinéraires : ces algorithmes ont été utilisés par la NASA pour la mission d'exploration de Mars, dans la gestion des déplacements du robot PathFinder. La société Sony les a aussi utilisés dans son robot Aibo. En effet, ce robot a « appris » à marcher dans un dispositif expérimental où son système de commande a été soumis à une évolution artificielle. Différents modes de commandes ont été testés, les plus performants ont été croisés et le résultat a été très positif. De génération en génération, le robot s'est redressé, puis a commencé à marcher en chutant souvent et a fini par marcher d'un pas assuré.

Informatique décisionnelle

Les algorithmes génétiques sont mis en œuvre dans certains outils d'informatique décisionnelle ou de datamining par exemple pour rechercher une solution d'optimum à un problème par mutation des attributs (des variables) de la population étudiée. Ils sont utilisés par exemple dans une étude d'optimisation d'un réseau de points de vente ou d'agences (banque, assurance, ...) pour tenter de répondre aux questions :
- quelles sont les variables (superficie, effectif, ...) qui expliquent la réussite commerciale de telle ou telle agence ?
- en modifiant telle variable (mutation) de telle agence améliore-t-on son résultat ?

Les limites


- Le temps de calcul : bien que ces algorithmes soient plus performants que des algorithmes qui parcourent toutes les solutions, ils nécessitent tout de même de nombreux calculs, en particulier au niveau de la fonction d'évaluation.
- Ils sont aussi souvent difficiles à programmer. Certains paramètres comme la taille de la population n'étant pas facilement évaluables. Un autre point souvent difficile à programmer concerne la fonction d'évaluation. Celle-ci doit souvent prendre en compte plusieurs paramètres du problème qu'il faut considérer avec attention.
- Il faut aussi noter l'impossibilité d'être assuré, même après un nombre important de générations, que la solution que l'on a trouvé est la meilleure. On peut seulement être sûr que l'on s'est approché de la solution optimale, sans la certitude de l'avoir atteinte.
- Un autre problème important est celui des optimums locaux. En effet, lorsqu'une population évolue, il se peut que certains individus qui à un instant occupent une place importante au sein de cette population deviennent majoritaires. À ce moment, il se peut que la population converge vers cet individu et s'écarte ainsi d'individus plus intéressants mais trop éloignés de l'individu vers lequel on converge. Pour vaincre ce problème, il existe différentes méthodes comme l'ajout de quelques individus générés aléatoirement à chaque génération, des méthodes de sélection différentes de la méthode classique ...

Schéma pour simplifier

assurance #Population de base générée aléatoirement #:n chaînes de caractères ou de bits.
#:1 chaîne correspond à 1 chromosome.
#Évaluation #:à chaque chaîne, une note correspondant à son adaptation au problème. #Sélection #:tirage au sort de n/2 couples de chaînes sur une roue biaisée. #:Chaque chaîne a une probabilité d’être tirée proportionnelle à son adaptation au problème. #:Optimisation possible : si l’individu le plus adapté n’a pas été sélectionné, il est copié d’office dans la génération intermédiaire à la place d’un individu choisi aléatoirement. #Croisement et mutation #:Chaque couple donne 2 chaînes filles. #
- Crossing-over. Probabilité : 70 %. Emplacement du crossing-over choisi aléatoirement. #
- :Exemple : #
- ::Chaînes parents : A : 00110100 ; B : 01010010 #
- ::Chaînes filles : A’ : 00010010 ; B’ : 01110100 #
- :Croisement en 2 points plus efficace. #
- Mutations des chaînes filles. Probabilité : de 0,1 à 1%. #
- :Inversion d’un bit au hasard ou remplacement au hasard d’un caractère par un autre. #
- :Probabilité fixe ou évolutive (auto-adaptation). #
- :On peut prendre probabilité = 1/nombre de bits. Les algorithmes génétiques reprennent la théorie de Darwin : sélection naturelle de variations individuelles : les individus les plus adaptés (the fitness) tendent à survivre plus longtemps et à se reproduire plus aisément. Amélioration de la population très rapide au début (recherche globale) ; de plus en plus lente à mesure que le temps passe (recherche locale).
Convergence : la valeur moyenne de la fonction d’adaptation a tendance à se rapprocher de celle de l’individu le plus adapté : uniformisation croissante de la population. Le temps de calcul des algorithmes génétiques croît en n ln n, n étant le nombre de variables.

Voir aussi


- Les algorithmes à estimation de distribution sont une généralisation des algorithmes génétiques

Références


- Charles Darwin: The origin of species (1859)
- J. H. Holland: Adaptation In Natural And Artificial Systems, University of Michigan Press (1975)
- La robotique évolutive dans Pour la science, n° 284, p. 70 (juin 2001)
- M. Mitchell: An introduction to genetic algorithm, MIT press (1996)
- Comment l'ordinateur transforme les sciences dans Les Cahiers de Science et Vie, n° 53 (1999)
- D. Goldberg : « Algorithmes génétiques », Addison-Wesley France (1994)

Liens externes


- Cours gratuit « Optimisation et algorithmes génétiques » : http://www.polytech-lille.fr/~vmagnin/coursag/ Génétique Catégorie:Métaheuristique Catégorie:Intelligence artificielle ja:遺伝的アルゴリズム th:ขั้นตอนวิธีเชิงพันธุกรรม

Algorithme

ko:알고리즘 ja:アルゴリズム th:อัลกอริทึม Catégorie:Algorithmique On nomme algorithmique la science des algorithmes, visant à étudier les opérations nécessaires à la réalisation d'un calcul. On parle également de procédé ou de procédure. Une recette de cuisine constitue par exemple un algorithme parfaitement défini.

Historique

Antiquité

Les algorithmes dont on a retrouvé des descriptions exhaustives ont été utilisés dès l'époque des Babyloniens, pour des calculs concernant le commerce et les impôts. L'algorithme le plus célèbre est celui attribué à Euclide permettant de trouver le plus grand commun diviseur de deux nombres.

Etude systématique

L'algorithmique a été systématisée par le mathématicien persan Al Kwarizmi (780-850), auteur d'un ouvrage décrivant des méthodes de calculs algébriques (ainsi que d'un autre introduisant le zéro des Indiens). Son nom donna au moyen-âge le nom "algorisme" qui devint algorithme avec lady Ada Lovelace, fille de lord Byron et assistante de Charles Babbage (1792-1871). On peut voir une allusion à la méthode algorithmique chez René Descartes dans le Discours de la méthode : « diviser chacune des difficultés que j'examinerois, en autant de parcelles qu'il se pourroit, et qu'il seroit requis pour les mieux résoudre. » Néanmoins, cette approche ne parle ni de boucles, ni d'itérations. Le substantif algorithmique désigne la méthode utilisant des algorithmes. Le terme est également employé comme adjectif. Un algorithme énonce une résolution sous la forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique. Les informaticiens utilisent fréquemment l'anglicisme implémentation pour désigner cette mise en œuvre. L'écriture en langage informatique est aussi fréquemment désignée par le terme « codage », qui n'a ici aucun rapport avec la cryptographie, mais qui se réfère au terme « code source » pour désigner le texte, en langage de programmation, constituant le programme. L'algorithme devra être plus ou moins détaillé selon le niveau d'abstraction du langage utilisé ; autrement dit, une recette de cuisine doit être plus ou moins détaillée en fonction de l'expérience du cuisinier.

Exemples d'algorithme

Il existe un certain nombres d'algorithmes classiques, utilisés pour résoudre des problèmes ou plus simplement pour illustrer des méthodes de programmation. On se réfèrera aux articles suivants pour de plus amples détails :
- Tours de Hanoï, problème célèbre illustrant la programmation récursive.
- Problème du tri, ou comment trier un ensemble de nombres le plus rapidement possible.
- Problème des huit dames, placer huit dames sur un échiquier sans qu'elles puissent se prendre entre elles.

Complexité algorithmique

La principale notion mathématique dans le calcul du coût d'un algorithme précis sont les notions de négligeabilité (notée o(f(n)), « petit o ») et de domination (notée O(f(n)), « grand o »), où f est une fonction mathématique de n, variable désignant la quantité d'informations (en bits, en nombre d'enregistrements…) manipulée dans l'algorithme. Les fonctions mathématiques relèvent de l'analyse. En algorithmique on trouve souvent des complexités du type :
- O(1) indépendant de la taille de la donnée
- O(log(n)), complexité logarithmique
- O(n), complexité linéaire
- O(n log(n)), complexité quasi-linéaire
- O(n^), complexité quadratique
- O(n^), complexité cubique
- O(n^p), complexité polynômiale
- O(n^), complexité quasi-polynômiale
- O(2^), complexité exponentielle
- O(n!), complexité factorielle Sans entrer dans les détails mathématiques, on peut dire que lorsque l'on calcule l'efficacité d'un algorithme (sa complexité algorithmique), on cherche davantage à connaître l'évolution du nombre d'instructions de base en fonction de la quantité de données à traiter (par exemple, dans un algorithme de tri, le nombre de lignes à trier), que le coût exact en secondes et en quantité de mémoire. Baser le calcul de la complexité d'un algorithme sur le temps qu'un ordinateur particulier prend pour effectuer le-dit algorithme ne permet pas de prendre en compte la structure interne de l'algorithme ni la particularité de l'ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d'accès aux données ou même l'exécution de l'algorithme (qui peut faire intervenir le hasard) le temps d'exécution ne sera pas le même.

Quelques indications sur l'efficacité des algorithmes

Souvent, l'efficacité d'un algorithme n'est connue que de manière asymptotique, c'est-à-dire pour de grandes valeurs du paramètre n. Lorsque ce paramètre est suffisamment petit, un algorithme de complexité supérieure peut en pratique être plus efficace. Ainsi, pour trier un tableau de 30 lignes (c'est un paramètre de petite taille), il est inutile d'utiliser un algorithme évolué comme Quicksort (l'un des algorithmes de tri les plus efficaces en moyenne) : l'algorithme de tri le plus trivial sera suffisamment efficace. À noter aussi : entre deux algorithmes dont la complexité est identique, on cherchera à utiliser celui dont l'occupation mémoire est la plus faible. L'analyse de la complexité algorithmique peut également servir à évaluer l'occupation mémoire d'un algorithme. Enfin, le choix d'un algorithme plutôt qu'un autre doit se faire en fonction des données que l'on s'attend à lui fournir en entrée. Ainsi, le Quicksort (ou tri rapide), lorsque l'on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l'applique à une liste de valeur ... déjà triée ! Il n'est donc pas judicieux de l'utiliser si on prévoit que le programme recevra en entrée des listes à peu près triées. Un autre paramètre à prendre en compte est la localité de l'algorithme. Par exemple pour un système à mémoire virtuelle qui dispose de peu de mémoire (par rapport au nombre de données à traiter), le Tri rapide sera normalement plus efficace que le Tri par tas car le premier ne passe qu'une seule fois sur chaque élément de la mémoire tandis que le second accède à la mémoire de manière discontinue (ce qui augmente le risque de "swapping").

Les heuristiques

Pour certains problèmes, les algorithmes ont une complexité beaucoup trop grande pour obtenir un résultat en temps raisonnable, même si l'on pouvait utiliser une puissance de calcul phénoménale. On est donc amené à rechercher une solution la plus proche possible d'une solution optimale en procédant par essais successifs. Puisque toutes les combinaisons ne peuvent être essayées, certains choix stratégiques doivent être faits. Ces choix, généralement très dépendants du problème traité, constituent ce qu'on appelle une heuristique. Le but d'une heuristique est donc de ne pas essayer toutes les combinaisons possibles avant de trouver celle qui répond au problème, afin de trouver une solution approchée convenable (qui peut être exacte dans certains cas) dans un temps raisonnable. C'est ainsi que les programmes de jeu d'échecs, de jeu de go (pour ne citer que ceux-là) font appel de manière très fréquente à des heuristiques qui modélisent l'expérience d'un joueur. Certains logiciels antivirus se basent également sur des heuristiques pour reconnaître des virus non répertoriés dans leur base, en s'appuyant sur des ressemblances avec des virus connus.

Applications


- Cryptologie et Compression de données
- Structure de données, Algorithmes de tri et Recherche dichotomique
- Allocation de mémoire et ramasse-miettes
- Informatique musicale
- Algorithme génétique en informatique décisionnelle

Voir aussi


- Al-Khuwarizmi
- Algorithme récursif
- Algorithme réparti
- Langage K
- Métaheuristique
- Structure de contrôle

Liens externes


- [http://www-ipst.u-strasbg.fr/pat/program/algo.htm Introduction à l'algorithmique, avec des exemples en langage C]
- [http://www.pise.info/algo/codage.htm Initiation à l'algorithmique]
- [http://www.myalgorithm.com Algorithmes de base dans plusieurs langages de programmation]

Sélection naturelle

En biologie, la sélection naturelle est un aspect de la théorie de l'évolution décrite par Charles Darwin. La sélection provient du fait qu'il naît tôt ou tard plus d'individus qu'il ne peut en vivre, les ressources n'étant pas infinies (voir Malthus). Si les caractéristiques des individus présentent des variations et que celles-ci sont héréditaires, les variations les plus propices à la survie et à la reproduction se transmettront mieux que les autres.

Principe

Quand les modifications sont neutres pour ces deux fonctions, on parle de dérive, voire (si le groupe est très réduit) d'effet fondateur. Quand ces modifications produisent une tendance vérifiable sur des générations, on parle de sélection. Notons que si des caractères acquis étaient héréditaires (hypothèse de Lamarck), le principe de cette sélection s'appliquerait là encore, et Darwin l'envisage explicitement dans L'Origine des espèces.

Position

L'adjectif naturelle s'oppose chez Darwin au concept de sélection artificielle connue et pratiquée depuis quelques milliers d'années par les éleveurs. La sélection naturelle, moins rapide, se compose
- d'une sélection de survie (atteindre les proies, échapper aux prédateurs, gérer les parasites et germes de maladie)
- d'une sélection sexuelle (obtenir une descendance : séduire ou forcer un partenaire) sur laquelle Darwin insiste suite à ses obervations dans les Galapagos, mais qui fut un peu négligée par ses continuateurs jusque vers la fin du XXème siècle où Stephen Jay Gould remit l'accent sur cette notion. Et tout cela mieux que les congénères (et les autres espèces proches), y compris à leur détriment, aspect là encore remis en lumière par Stephen Jay Gould.

Pression de sélection

Les modifications successives des générations dans les populations naturelles sont 'orientées' par les pressions intérieures (séduction, compétition dans l'espèce) et extérieures à l'espèce (limitation des ressources, modifications de l'environnement, prédateurs, parasites...), bref, ce qui influence la survie et la reproduction des individus. La sélection naturelle apparaît quand les conditions suivantes sont réunies :
- renouvellement d'une population d'individus par mortalité et reproduction;
- variabilité de caractères au sein des individus d'une population à un instant donné;
- héritabilité de certains de ces caractères variables, c'est-à-dire corrélation forte entre ces caractères chez un individu et ces caractères chez ses parents, ou plus généralement, ses ancêtres;
- variabilité du nombre de descendants;
- interaction non aléatoire entre les caractères variables héritables et l'environnement pour déterminer statistiquement l'importance de la descendance d'un individu. Il en découle alors que l'environnement détermine une orientation des modifications successives des générations. Ces conditions peuvent être simulées et le phénomène vérifié (référence au domaine de la recherche informatique sur la vie artificielle à mettre).

Détail sur la sélection sexuelle

La sélection sexuelle selon Darwin est l'idée que, chez les espèces à reproduction sexuée, les modifications successives des générations sont aussi influencées par les critères de choix des partenaires sexuels. Il s'agit ici d'un phénomène interne à l'espèce, même s'il interfère souvent avec la sélection naturelle résultant d'influences externes. La sélection sexuelle est invoquée pour expliquer des caractères ou des comportements qui pénalise la survie quand ils sont analysés en dehors du contexte reproductif, comme la queue du paon, les bois des megaceros, ou le suicide de l'araignée mâle. S'il s'agit dans ces cas d'exemples extrêmes, le phénomène est général à des degrés divers : dans la plupart des espèces (d'oiseaux, de mammifères, de poissons, d'insectes...) les mâles (en général, il y a de rares cas où il s'agit des femelles) ont des caractères qui vont à l'encontre de leur survie (mais qui n'interfère pas négativement avec leur potentiel reproductif, au contraire) : attributs voyants (couleurs, attitudes) ou encombrants, comportements qui exposent plus au danger, etc. Du point de vue des femelles, tant qu'il reste suffisamment de mâles (et c'est presque toujours le cas), tout facteur aussi absurde soit-il qui augmente la pression de sélection sur les mâles (même si c'est au prix d'une mortalité plus forte), constitue un avantage : les performances dans les "autres compartiments du jeu" (santé, performance physique ou intellectuelle, etc.) n'en auront que plus d'importance, ce qui sera tout bénéficie pour les descendant de la femelle. Ainsi, pour une femelle, choisir un mâle qui a survécu malgré une exposition plus importante est un indice qu'il dispose d'avantages significatifs. Tout compte fait, une femelle paon qui accepterait un mâle moins "beau" non seulement ne gagne aucun avantage sur ses congénères (qui trouvent un mâle aussi facilement qu'elle), et se prive d'un indice significatif dans les autres domaines. Il est donc avantageux même pour les femelles de choisir un mâle qui participe à cette compétition aussi absurde qu'elle paraisse. La même analyse explique que, inversement, les mâles n'ont aucun intérêt à courtiser préférentiellement des femelles participant à une compétition absurde du même genre, mais au contraire doivent s'interesser des indices de fécondité réelle Les deux pressions s'observent facilement dans l'espèce humaine.

Relation avec la génétique

Dans sa forme générale, et dans sa forme originale due à Darwin, la notion de sélection naturelle ne nécessite pas de théorie sur la génétique. Darwin et Mendel vécurent à la même époque, mais ne correspondirent jamais ! La génétique donna néanmoins des bases précises pour décrire la transmission des caractères. Cela a permis le développement au milieu du de la génétique des populations, qui propose des modèles mathématiques aux différentes formes de sélection, et permet ainsi de quantifier ces phénomènes. Catégorie:Théorie Catégorie:Biologie de l'évolution ja:自然選択説

1960

Cette page concerne l'année 1960 du calendrier grégorien.

Événements

Premier trimestre

Détails : Janvier 1960 - Février 1960 - Mars 1960
- 1 janvier : En France, Entrée en vigueur du nouveau franc par division de l'ancien par 100.
- 1 janvier : Indépendance du Cameroun, président Ahmadou Ahidjo.
- 9 janvier : Début de la construction du barrage d'Assouan en Égypte.
- 11 janvier : Indépendance du Tchad, président Tombalbaye.
- 24 janvier : En Algérie, semaine des barricades à Alger (24 janv.-1er fév.).
- 5 février : Le plus grand synchrotron du monde pour la recherche nucléaire (25-milliards d'électron-volt), est inauguré à Meyrin dans la banlieue de Genève (Suisse) par un groupement de 13 nations européennes.
- 13 février : Premier essai (Gerboise bleue) de la bombe à fission française (bombe A) à Reggane dans le désert du Tanezrouf (Sahara algérien).
- 18 février : Ouverture des 8 Jeux Olympiques d'hiver à Squaw Valley en Californie.
- 28 février : Création à Atlanta du mouvement des chevaliers du Ku Klux Klan regroupant les mouvements racistes disparates de 17 états méridionaux.
- 29 février : Un tremblement de terre de magnitude 6,7 sur l'échelle de Richter fait 15 000 victimes à Agadir au Maroc.
- 2 mars : Le pape nomme les premiers cardinaux non blancs : un Africain, un Japonais et un Philippin.
- 7 mars : Lancement du journal Télé 7 jours
- 21 mars : Massacre à Sharpeville, en Afrique du Sud. La Police ouvre le feu sur un groupe de manifestants noirs non armés : 69 morts et 180 blessés.
- 23 mars : Visite en France de Nikita Khrouchtchev

Deuxième trimestre

Détails : Avril 1960 - Mai 1960 - Juin 1960
- 3 avril : Fondation du PSU
- 18 avril : Première apparition publique des Beatles.
- 27 avril : Indépendance du Togo octroyée par la France. Ancienne colonie allemande, le pays était sous administration déléguée de l'ONU.
- 1 mai : Un avion de reconnaissance américain de type U2 (avion-espion) est abattu au-dessus du territoire soviétique.
- 7 mai : Nikita Khrouchtchev accède à la présidence de l'URSS.
- 9 mai : Légalisation de la pilule anticonceptionnelle sur la territoire américain. La FDA (Food and Drug Administration) approuve la pilule comme moyen contraceptif.
- 11 mai :
  - Mise à flot du paquebot France, à Saint-Nazaire (Bretagne).
  - Le Président Eisenhower reconnaît publiquement que les États-Unis ont effectué des missions de reconnaissance aérienne au-dessus de territoire soviétique durant les quatre dernières années. Le 15 mai, il annonce que plus aucun vol d'espionnage ne sera fait.
- 14 mai : Sommet des quatre grandes puissances, à Paris, avec Eisenhower, Macmillan, Khrouchtchev et de Gaulle.
- 22 mai : Tremblement de terre record au Chili (9,5 sur l'échelle de Richter), il fait 2000 morts sur place et 250 du fait des tsunamis au Japon, aux Philippines, en Alaska et aux îles Hawaï.
- 23 mai : Enlèvement de Adolf Eichmann en Argentine par les Israéliens pour être jugé en Israël.
- 20 juin : Indépendances du Mali et du Sénégal octroyées par la France. Les deux pays forment la Fédération du Mali qui éclatera au mois d'août.
- 30 juin : Indépendance du Congo Belge octroyée par la Belgique, président Joseph Kasavubu. La guerre civile débute immédiatement.

Troisième trimestre

Détails : Juillet 1960 - Août 1960 - Septembre 1960
- 1 juillet :
  - Le Somaliland britannique et la Somalie sont réunis et proclament leur indépendance.
  - Indépendance du Ghana octroyée par la Grande-Bretagne mais le pays reste membre du commonwealth.
- 9 juillet : Un décret autorise le péage sur les autoroutes françaises.
- 11 juillet : À la convention nationale des démocrates à Los Angeles en Californie, le sénateur John F. Kennedy est nommé dès le premier tour de vote. C'est le plus jeune candidat à être nommé pour cette élection.
- 13 juillet : Premier festival de Jazz d'Antibes en France.
- 20 juillet : Pour la première fois au monde, une femme Sirimavo Bandaranaike est élue chef d'un gouvernement à Ceylan.
- : Indépendance du Dahomey (Bénin actuel) octroyée par la France.
- 3 août : Le record du monde de vitesse dans l'air a été battu avec 2 196 mi/h (milles par heure). Il a été établi par la fusée expérimentale américaine X-15.
- 5 août : Indépendance de la Haute-Volta (actuel Burkina Faso) octroyée par la France.
- 7 août :
  - Indépendance de la Côte d'Ivoire octroyée par la France.
  - Nationalisation des entreprises américaines sur le territoire cubain par Fidel Castro
- 15 août : Indépendance de la république populaire du Congo (Congo Brazzaville) octroyée par la France.
- 16 août : Indépendance de Chypre octroyée par la Grande-Bretagne après 88 ans d'occupation coloniale.
- 16 août : Joseph Kittinger saute en parachute à partir d'un ballon à 31 333 m au-dessus du Nouveau-Mexique. Il bât les records de saut en haute-altitude, de la plus importante chute libre (25 700 mètres) avant ouverture du parachute, et la plus grande vitesse réalisée par un être humain (982 km/h) sans assistance motorisée
- 17 août : Indépendance du Gabon octroyée par la France.
- 20 août : Le Sénégal quitte la Fédération du Mali et déclare son indépendance.
- 25 août : Ouverture des 17 Jeux olympiques à Rome jusqu'au 11 septembre.
- 11 septembre : Clôture des 17 Jeux olympiques à Rome depuis le 25 août.
- 13 septembre : L'ouragan Donna, considéré comme le plus destructeur par les Américains, tue 30 personnes et laisse derrière lui des milliers des sans-abri sur la côte atlantique, de la Floride au Canada.
- 14 septembre : Coup d'État au Congo par le colonel Joseph Mobutu.
- 22 septembre : Modibo Keïta proclame l'indépendance de la République du Mali après l'échec de la Fédération du Mali.

Quatrième trimestre

Détails : Octobre 1960 - Novembre 1960 - Décembre 1960
- 1 octobre : L'indépendance du Nigeria est concédée par la Grande-Bretagne.
- 12 octobre : Le président soviétique Nikita Khrouchtchev frappe sur son pupitre avec sa chaussure à l'Assemblée générale de l'ONU pour protester de la discussion sur la politique de l'Union soviétique à l'égard de l'Europe de l'Est.
- 24 octobre : Explosion d'une fusée soviétique R 16 à Baïkonour : 123 morts.
- 29 octobre : Nikita Khrouchtchev promet, lors d'une interview, de fournir à Cuba des missiles pour prévenir une attaque américaine.
- 4 novembre : Le Président français Charles de Gaulle annonce à la TV algérienne un référendum sur l'autodétermination de l'Algérie.
- 8 novembre : Élection de John F. Kennedy (parti Démocrate) comme président des États-Unis avec 49,7 % des voix contre Richard Nixon (R) 49,5 %, et devenant le plus jeune Président des États-Unis (70 % des noirs américains auraient voté pour lui).
- 15 novembre : Indépendance de la Mauritanie octroyée par la France.
- 1 décembre : Indépendance de la République centrafricaine octroyée par la France.
- 9 décembre : Voyage du président Charles de Gaulle en Algérie, marquée par des émeutes sanglantes causant la mort de 127 personnes.
- 20 décembre : Création au Viêt Nam du Sud d'un Front de libération national. Début de la guerre du Viêt Nam.

Chronologies thématiques


- Aéronautique : 1960 en aéronautique
- Chemins de fer : 1960 dans les chemins de fer
- Cinéma : 1960 au cinéma
- Sport : 1960 en sport
- Arts et Culture : Arts et cultures en 1960
- Sciences et Techniques : Sciences et techniques en 1960

Naissances en 1960


- 24 janvier : Nastassja Kinski, actrice
- 19 février : Prince Andrew, second fils de la reine Elizabeth II d'Angleterre
- 29 février : Cheb Khaled, chanteur algérien
- 7 mars : Ivan Lendl, joueur de tennis tchèque
- 21 mars : Ayrton Senna, coureur automobile brésilien
- 18 mai : Yannick Noah, joueur de tennis français
- 22 mai : Hideaki Anno, réalisateur japonais
- 3 juillet :
  - Vince Clarke, musicien anglais des groupes Depeche Mode puis Erasure
  - Perrine Pelen, skieuse, française.
- 15 juillet : Kim Alexis, modèle américaine
- 12 août : Laurent Fignon, champion cycliste français
- 19 septembre : Hugh Grant, acteur américain
- 8 octobre : François Pérusse, humoriste québécois.
- 14 octobre : Olivier Mathieu, dit Robert Pioche, écrivain France.
- 30 octobre : Diego Maradona, champion argentin de football
- 25 novembre : John F. Kennedy Jr., fils du président John F. Kennedy
- 27 decembre : Maryam d'Abo, actrice britannique voir aussi::Catégorie:Naissance en 1960

Décès en 1960


- 2 janvier : Fausto Coppi, coureur cycliste italien, (° 1919).
- 4 janvier : Albert Camus, prix Nobel de littérature, écrivain français, (° 1913).
- 24 janvier : Edwin Fischer, pianiste suisse.
- 21 février :
  - Jacques Becker, réalisateur, acteur, scénariste français, (° 1906).
  - Samuel Mitchell, astronome (Il a calculé la distance de plus d'un millier d'étoiles), américain.
- 22 février : Paul-Émile Borduas, peintre surréaliste puis abstrait québécois, (° 1905).
- 3 avril : Norodom Suramit, roi du Cambodge.
- 28 avril : Anton Pannekoek, astronome et un militant communiste hollandais, (° 1873).
- 11 mai : John Davison Rockefeller Junior, milliardaire américain, (° 1874).
- 17 mai : Jules Supervielle, poète et écrivain français, (° 1884).
- 30 mai : Boris Pasternak "Docteur Jivago", écrivain russe, prix Nobel de littérature, (° 1890).
- 16 juillet : John P. Marquart, romancier américain
- 15 août : Jefferson Machamer (60 ans), artiste de dessins animés (The Baffles, Petting Patty et Guys and Gals).
- 7 septembre : Wilhelm Pieck (84 ans), ancien président communiste de l'Allemagne de l'Est.
- 16 septembre : J. Cheever Chowdin (71 ans), ancien patron de Universal Pictures.
- 26 septembre : Emily Post, la grande dame des bonnes manières.
- 12 octobre : Inejir Asanuma (61 ans). leader socialiste japonais (assassiné).
- 5 novembre :
  - Mack Sennett, réalisateur producteur américain d'origine canadienne, (° 1884)
  - Ward Bond, acteur américain (° 1903, 57 ans)
- 16 novembre : Clark Gable, acteur américain, (° 1901).
- 7 décembre : Clara Haskil, pianiste suisse d'origine roumaine.
- Philippe Panneton dit Ringuet (64 ans), écrivain canadien
- Richard Wright, écrivain américain qui traita des problèmes sociaux et psychologiques des noirs américains. voir aussi::Catégorie:Décès en 1960 __NOTOC__ Catégorie:1960 ja:1960年 ko:1960년 ms:1960 simple:1960 th:พ.ศ. 2503

Mutation

La mutation désigne le fait de changer, d'être modifié. En biologie, le terme mutation est utilisé pour désigner la modification de la séquence des bases, séquence dont l'ordonnancement donne toute sa signification à l'ADN et lui permet de coder les gènes.

Agents mutagènes

La mutation peut être causée par une multitude de facteurs appelés agents mutagènes, comme :
- Les ondes électromagnétiques.
- Des substances chimiques comme le benzène.
- Des erreurs de duplication lors de la mitose ou de la méiose, tout à fait normales (sans intervention extérieure).

Transmission de la mutation


- La mutation, si elle affecte les cellules germinales, peut être transmise aux descendants du sujet mutant : c'est la base du processus de l'évolution.
- En revanche, comme c'est le cas pour la plupart des mutations accidentelles (provoquées par irradiation ou substances chimiques), si elle n'affecte que des cellules somatiques,la mutation ne se transmet pas et n'affectera donc que le sujet l'ayant subie directement, appelé mutant.

Différents types de mutation

Les mutations peuvent être classées selon leurs conséquences moléculaires :
- Les mutations décalantes (ou mutations non-sens) se caractérisent en un décalage des acides aminés d'où une modification profonde de la protéine obtenue et le plus souvent un raccourcissement par l'apparition d'un codon-stop :
  - Une mutation par addition consiste en l'ajout d'un ou plusieurs acides aminés dans la chaîne polypeptidique.
  - Au contraire, une mutation par délétion se caractérise par le retrait d'acides aminés.
- Les mutations non-décallante (ou mutations faux-sens) induisent des modifications moins importantes (modification d'un ou de quelques peptides) :
  - Une mutation par substitution consiste en la transformation d'un acide aminé de l'ADN. Elles peuvent également être classés selon leurs conséquences phénotypiques :
- La plupart des mutations ont de plus ou moins importantes conséquences phénotypiques (certaines d'entre elles peuvent avoir des conséquences graves comme le cancer ou des maladies génétiques, car la modification d'un seul acide aminé dans la chaîne constituant une protéine peut modifier complètement sa structure spatiale, qui conditionne son fonctionnement).
- Les mutations neutres ne modifient pas le fonctionnement de la protéine et n'ont pas de conséquence phénotypique macroscopique.
- Les mutations silencieuses ou muettes n'entraînent aucun changement dans la séquence d'acides aminés, ce qui est dû aux nombreuses redondances dans le code génétique (le fait que plusieurs séquences différentes puissent avoir la même signification, et donc coder pour le même acide aminé) catégorie:Génétique Catégorie:Biologie de l'évolution ja:突然変異 ko:돌연변이

Génétique

La génétique (du grec genno γεννώ = donner naissance) est la science qui étudie la transmission des caractères héréditaires entre des géniteurs et leur descendance. Ce terme regroupe un nombre important de disciplines, la plupart associées à la biologie.

Histoire

L'étude de la transmission des caractères à la descendance était déjà pratiquée par les éleveurs, et on considère que les diverses races de chiens (Canis familiaris) proviennent de sélections successives de loups (Canis lupus) depuis 20 000 ans (il a été montré que ces deux espèces de Canis sont interfécondes). L'interprétation à partir d'une unité qui est le gène est plus récente (voir l'Historique). Lamarck réalisait des expériences pour comprendre si les caractères acquis se transmettaient d'une génération à l'autre. Louis Pasteur, en prouvant l'absence de génération spontanée, établit qu'un être vivant possède au moins un ancêtre dont il tire ses caractéristiques. La première étude sérieuse sur le sujet est réalisée par le moine Gregor Mendel, considéré comme pionnier de la génétique. En observant la transmission des caractéristiques morphologiques de pois à travers quelques générations, il définit les termes de phénotype et génotype et il énonce, en donnant un petit coup de pouce à ses chiffres, les lois dites de Mendel, base de la génétique moderne, et ce, bien avant la découverte de l'ADN. August Weismann postula en 1883 l'existence d'un support matériel de l'hérédité . Cette théorie défendait alors l'impossibilité de la transmission des caractères acquis (néolamarckisme) et demandait une pleine adhésion au darwinisme (les êtres vivants dérivent les uns des autres par petites variations fortuites continues passées au crible de la sélection naturelle). Hugo de Vries en Hollande, Carl Correns et Erich von Tschermak en Allemagne redécouvraient les lois de Mendel chez les végétaux en 1901. En Angleterre William Bateson deviendra le plus ardent défenseur des lois de Mendel, avec son livre, paru en 1902, Gregor Mendel’s principle of Heredity. Bateson fut en outre le premier à introduire en 1906 le terme de génétique. Cette redécouverte imposa l’idée que des particules matérielles indépendantes et juxtaposées (appelées plus tard gènes) se transmettaient, selon des lois statistiques immuables, de génération en génération. La France était à cette époque, du fait de sa tradition lamarckiste scientifique et sociale, bien loin d’accepter une telle idée. En 1902 pourtant, le biologiste, professeur à la Faculté des sciences de Nancy, Lucien Cuénot (1866-1951) retrouva ces lois chez l’animal. Puis il découvrit, en 1905, le premier cas de gène létal chez l’animal, le premier phénomène d’épistasie (1907) où plusieurs gènes situés à des endroits différents du chromosome interviennent dans la même voie biochimique, et, en 1908, le premier cas de pléïotropie où certains gènes peuvent agir sur plusieurs caractères en apparence indépendants. Entre 1908 et 1912, il démontra l’origine héréditaire de certains cas de cancer. En outre, dès 1903, il proposa une interaction possible entre mnémon (gène), diastase (enzyme) et pigments (protéine) ce qui, dans le contexte français de l'époque, était une prouesse. Aux Etats-Unis, T.H. Morgan et son équipe développèrent dès 1910 la théorie chromosomique de l’hérédité, à partir de la drosophile, mouche d'élevage aisé et de reproduction bien plus rapide que la souris blanche. Il postula l'échange d'unités chromosomiques pendant la méiose et mit au point une méthode qui permit de situer approximativement la position des gènes sur les chromosomes. Les progrès techniques permettent peu à peu de définir la notion de gène. Il faut attendre les progrès de la microscopie pour localiser le support des gènes : le chromosome. Dans les années 50, un nouveau pas est franchi par les Américains James Watson et Francis Crick qui déterminent la structure fine de la molécule constituant les gènes, l'ADN, et aident ainsi à comprendre les mécanismes moléculaires de l'hérédité. Un peu plus tard, trois autres Nobel, François Jacob, André Lwoff et Jacques Monod, montrent comment celui-ci se structure en codons pour programmer la synthèse de protéines à partir d'acides aminés, la redondance des codages, le mécanisme des mutations, et la présence d'un code de fin de lecture, comme sur une bande magnétique. Depuis, les études génétiques permettent peu à peu de comprendre la façon dont l'information génétique est codée dans les chromosomes. On a découvert aussi qu'une grande partie de l'ADN était non-codant. Plus récemment, on a découvert une hérédité basée sur l'ADN mitochondrial. Cet ADN est à l'origine de maladie transmises exclusivement par la mère. En effet lors de la fécondation, les mitochondries du spermatozoïde paternel ne pénètrent pas dans l'ovocyte maternel et les mitochondries ont (sauf chez de très rares exceptions) une origine exclusivement maternelle.

Les différents champs de recherche

Très tôt, la génétique est diversifiée en plusieurs branches différentes. L'hérédité, qui étudie le phénotype et tente de déterminer le génotype sous-jaçant se base toujours sur les lois de Mendel. La biologie cellulaire et la biologie moléculaire étudient les gènes et leur support matériel (ADN ou ARN) au sein de la cellule, la biologie cellulaire pour leur expression. Les progrès de la branche ingénierie de la génétique, le génie génétique, a pu passer le stade de la simple étude en permettant de modifier le génome, d'implanter, supprimer ou modifier de nouveau gènes dans des organismes vivants : il s'agit des Organisme génétiquement modifié (OGM). Les mêmes progrès ont ouvert une nouvelle voie d'approche thérapeutique : la « thérapie génique ». Il s'agit d'introduire de nouveaux gènes dans l'organisme afin de pallier une déficience héréditaire. L'évolution sans cesse croissante de la connaissance en génétique pose plusieurs problèmes éthiques, liés au clonage, aux divers type d'eugénisme possibles, à la propriété intellectuelle de gènes et aux possibles risques environnementaux dus aux OGM, comme elle complique également la compréhension du fonctionnement de la machinerie cellulaire. En effet, plus on l'étudie, plus les acteurs sont nombreux (ADN, ARN messager, de transfert, microARN, etc.) et le nombre de rétro-actions (épissage, édition, etc.) entre ces acteurs grandit.

Chronologie

En 1865, passionné de sciences naturelles, le moine autrichien Gregor Mendel, dans le jardin de la cour de son monastère, décide de travailler sur des pois comestibles présentant sept caractères (forme et couleur de la graine, couleur de l'enveloppe, etc.), dont chacun peut se retrouver sous deux formes différentes. À partir de ses expériences, il publie un article de génétique « Recherche sur les hybrides végétaux » où il énonce les lois de transmission de certains caractères héréditaires. Cet article est envoyé aux scientifiques des quatre coins du monde, les réactions sont mitigées, voire inexistantes. Ce n'est qu'en 1907 que son article fut reconnu et traduit en français. En 1869 l' ADN est isolée par Friedrich Miescher, un médecin suisse. Il récupère les bandages ayant servis à soigner des plaies infectées et il isole une substance riche en phosphore dans le pus. Il nomme cette substance nucléine. Il trouve la nucléine dans toutes les cellules et dans le sperme de saumon. En 1879, Walter Flemming décrit pour la première fois une mitose. La mitose avait déjà été décrite 40 ans avant par Carl Nageli mais celui ci avait interprété la mitose comme une anomalie. Walter Flemming invente les termes prophase, métaphase, et anaphase pour décrire la division cellulaire. Son travail est publié en 1882. En 1880, Oskar Hertwig et Eduard Strasburger découvrent que la fusion du noyau de l'ovule et du spermatozoide est l'élément essentiel de la fécondation. En 1900, redécouverte des lois de l'hérèditè par Hugo de Vries, Carl Correns et Erich von Tschermak-Seysenegg redécouvrent de façon indépendante les lois de Mendel. En 1902, Walter Sutton observe pour la première fois une méiose propose la théorie chromosomique de l'hérédité, c'est-à-dire que les chromosomes seraient les supports des gènes. Il remarque que le modèle de séparation des chromosomes supporte tout à fait la théorie de Mendel. Il publie son travail la même année. Sa théorie sera démontrée par les travaux de Thomas Morgan.
Première description d'une maladie humaine héréditaire par Archibald Garrod : l' alcaptonurie. En 1909, Wilhelm Johannsen crée le terme gène et fait la différence entre l'aspect d'un être (phénotype) et son gène (génotype). William Bateson quatre ans avant utilisé le terme génétique dans un article et la nécessité de nommer les variations héréditaires. En 1911, Thomas Morgan découvre une drosophile (mouche) mutante aux yeux blancs. Il montre les chromosomes sont les supports des gènes. Il découvre la liaison génétique (genetic linkage) et les recombinaisons génétiques. il travaille avec Alfred Sturtevant, Hermann Muller, et Calvin Bridges . Il reçoit le prix Nobel de Médecine en 1933. Ses expériences permettront de consolider la théorie chromosomique de l'hérédité. En 1913, Morgan et Alfred Sturtevant publient la première carte génétique du chromosome X de la drosophile, montrant l'ordre et la succession des gènes le long du chromosome. En 1941, George Beadle et Edward Tatum émettent l'hypothèse qu'un gène code pour un (et uniquement un) enzyme en étudiant Neurospora crassa . En 1943, la diffraction au rayon X de l'ADN par William Astbury permet d'émettre la première hypothèse concernant structure de la molécule : une structure régulière et périodique qu'il décrit comme une pile de pennies (like a pile of pennies). En 1944, Oswald Avery, Colin MacLeod, and Maclyn McCarty démontre que l'ADN est une molécule associée à une information héréditaire et peut transformer une cellule..
Barbara McClintock montre que les gènes peuvent se déplacer et que le génome est beaucoup moins statique que prèvu . Elle reçoit le prix Nobel de Médecine en 1983. En 1952, Alfred Hershey et Martha Chase découvrent que seul l'ADN d'un virus a besoin de pénétrer dans une cellule pour l'infecter. Leur travaux renforcent considérablement l'hypothèse que les gènes sont faits de DNA. En 1953, simultanément aux travaux de recherche de Maurice Wilkins et Rosalind Franklin qui réalisèrent un cliché d'une molécule d'ADN, James Watson et Francis Crick présentent le modèle en double hélice de l'ADN, expliquant ainsi que l'information génétique puisse être portée par cette molécule. Watson, Crick et Wilkins recevront en 1962 le prix Nobel de médecine pour cette découverte. En 1955, Joe Hin Tjio fait le premier compte exact des chromosomes humains : 46 . Arthur Kornberg découvre la DNA polymerase, un enzyme permettant la réplication de l'ADN. En 1957, le mécanisme de réplication de l'ADN est mis en évidence. Dans les années 60, François Jacob et Jacques Monod élucident le mécanisme de la synthèse de protéines. Le principe de code génétique est admis. Ils montrent que la régulation de cette synthèse fait appel à des protéines et mettent en évidence l'existence de séquences d'ADN non traduites mais jouant un rôle dans l'expression des gènes. 1968 : prix Nobel décerné pour le déchiffrage du code génétique. 1975 : autre prix Nobel pour la découverte du mécanisme de fonctionnement des virus La génomique devient dès lors l'objet d'intérêts économiques importants. En 1989, il est décidé de décoder les 3 milliards de paires de bases du génome humain pour identifier les gènes afin de comprendre, dépister et prévenir les maladies génétiques et tenter de les soigner. Une première équipe se lance dans la course : le Human Genome Project, coordonné par le NIH (National Institutes of Health) et composé de 18 pays dont la France avec le Génoscope d'Évry. Dans les années 1990, à Évry, des méthodologies utilisant des robots sont mises au point pour gérer toute l'information issue de la génomique. En 1992-1996, les premières cartes génétiques du génome humain sont publiées par Weissenbach dans un laboratoire du Généthon. En 1998, créée par Craig Venter et Perkin Elmer (leader dans le domaine des séquenceurs automatiques), la société privée Celera Genomics commence elle aussi à assembler le génome humain en utilisant une autre technique que celle utilisée par le NIH. En 1999, un premier chromosome humain, le 22, est séquencé par une équipe coordonnée par le centre Sanger, en Grande-Bretagne. En juin 2000, le NIH et Celera Genomics annoncent chacun l'obtention de 99% de la séquence du génome humain. Les publications suivront en 2001 dans les journaux Nature pour le NIH et Science pour Celera Genomics. Le 14 avril 2003, la fin du séquençage du génome humain est annoncée.

Voir aussi

Liens internes


- transmission héréditaire, transmission génétique ;
  - Mitose ;
  - Méiose ;
  - Chromosome ;
  - Gène ;
    - ADN,
    - Les innovations génétiques,
- bioéthique ;
- bioinformatique ;
- Gregor Mendel ;
- Charles Darwin ;
- Denis Buican;
- Jean-Baptiste Lamarck.
- techniques et méthodes
- Lucien Cuénot

Références


- Sutton, Walter, "The chromosomes in heredity", Biological Bulletin 4 (1903): 231-251.
- Garrod, A. E. "The incidence of alkaptonuria: a study in chemical individuality". Lancet II: 1616-1620, 1902.
- Morgan, Thomas Hunt, et. al., "The mechanism of Mendelian heredity", (New York: Henry Holt and Co., 1915)
- Beadle, G. and Tatum, E., "Genetic control of biochemical reactions in Neurospora". Proc Natl Acad Sci 27: 499-506, 1941
- Avery, Oswald T., MacLeod, Colin M., and McCarty, Maclyn, "Studies on the Chemical Nature of the Substance Inducing Transformation of Pneumococcal Types: Induction of Transformation by a Deoxyribonucleic Acid Faction Isolated from Pneumococcus Type III". Journal of Experimental Medicine 149 (February 1979): 297-326. (Reprint of 1944 paper).
- McClintock, Barbara, "The origin and behavior of mutable loci in maize", Proceedings of the National Academy of Sciences 36 (6): 344-355, 1950
- Tjio and Levan: "The chromosome number in man". Hereditas 42: 1, 1956.

Liens externes


- [http://www.ensembl.org/index.html Base de données libre sur la génétique humaine]
- ja:遺伝学 ko:유전학 ms:Genetik simple:Genetics th:พันธุศาสตร์

Chromosome


- Catégorie:Genre sexuel Un chromosome (du grec chroma, couleur et soma, corps, élément) est un élément microscopique constitué d'une molécule d'ADN et de protéines. On trouve les chromosomes dans le noyau des cellules eucaryotes Il prend la forme soit d'un bâtonnet, soit d'un écheveau, selon qu'il est condensé ou non. Les détails donnés ici correspondent aux chromosomes d'organismes eucaryotes. Il existe plusieurs distinctions à faire par rapport aux chromosomes bactériens (procaryote). procaryote Au figuré, le mot chromosome est utilisé pour décrire son contenu en terme d'information génétique. Les chromosome portent les gènes, supports de l'information génétique transmis des cellules mères aux cellules filles lors de la mitose ou de la méiose (reproduction sexuée). Les chromosomes sont habituellement représentés par paires, en parallèle avec leur homologue. Ils sont souvent illustrés sous leur forme condensée et dupliquée (en métaphase de la mitose). Les chromosomes sont en nombre variable suivant chaque espèce. L'espèce humaine en compte 46 : 23 paires, dont 22 sont des chromosomes homologues (autosomes), la dernière paire correspondant aux deux chromosomes sexuels (gonosomes). Les chromosomes humains sont numérotés de 1 à 22, du plus long au plus court, et les deux chromosomes sexuels sont nommés X et Y. Cette règle n'est pas la même pour tous les organismes. L'ensemble des chromosomes est représenté sur un caryotype, ou carte de chromosomes. Après leur réplication pendant l'interphase du cycle cellulaire, les chromosomes sont composés de deux copies identiques de chromatides, attachées entre-elles au niveau d'un centromères. Chaque chromatide est formée d'une molécule d'ADN (le nucléofilament) associée à des protéines histones - assemblées en nucléosomes - et des protéines non histones. En microscopie optique, on distingue sur les chromosomes des régions condensées, formées d'hétérochromatine, et des régions décondensées, formées d'euchromatine. Les gènes exprimés se localisent principalement au niveau de l'euchromatine. La mitose transmet la totalité des chromosomes aux cellules filles, tandis que la méiose ne transmet que la moitié du patrimoine génétique aux cellules filles, ce qui permet l'augmentation de la diversité du patrimoine génétique par le phénomène de recombinaison génétique.

Chromosomes bactériens

Les chromosomes bactériens sont souvent circulaires mais parfois ils sont linéaires. Quelques bactéries n'ont qu'un seul chromosome, alors que d'autres en ont un faible nombre. L'ADN des bactéries existe aussi sous forme de plasmides. La distinction entre plasmides et chromosomes est vague, bien que leur taille et leur importance soient généralement prises en compte. Les chromosomes bactériens initient la réplication.

Chromosomes chez les eucaryotes

Les eucaryotes possèdent de multiples chromosomes linéaires contenus dans le noyau cellulaire. Chaque chromosome a son propre centromère, avec un ou deux bras se projetant à partir de celui-ci. La fin des chromosomes sont des structures spéciales appelées télomères. La réplication de l'ADN commence à divers endroits du chromosome.

Chromosomes des différentes espèces


fertilization

Chromatine

Deux types de chromatine peuvent être distingués :
- L'euchromatine, qui consiste en ADN actif, par exemple exprimé en protéine.
- L'hétérochromatine, qui consiste en ADN principalement inactif. Il semble servir à des fins structurelles durant les phases chromosomiques. L'hétérochromatine peut à son tour se subdiviser en deux types :
  - Lhétérochromatine constitutive, qui n'est jamais exprimée. Elle est située autour du centromère et consiste en général en des séquences répétitives.
  - Lhétérochromatine facultative, qui est parfois exprimée. hétérochromatine. (Deux copies de the molécules d'ADN sont présentes) (5) au cours de la métaphase.]]

Caryotype

Chromosome humain


- Le projet du génome humain visait à la seule détermination de la portion euchromatique du génome. Les [télomère]]s, centromères et autres régions hétérochromatiques n'ont pas encore été déterminées, ainsi d'ailleurs qu'un petit nombre de lacunes non clonables [http://www.ncbi.nlm.nih.gov/genome/seq/]

Altérations des chromosomes

Les altérations des chromosomes sont :
- les cassures chromosomiques, comme la délétion ou l'inversion ;
- les échanges de fragments entres chromosomes : translocation et insertion ;
- la duplication.

Exemples


- Syndrome du cri du chat, due à une délétion d'une partie du bras court du chromosome 5.
- Syndrome de Wolf-Hirschhorn, due à une délétion partielle du bras court du chromosome 4.
- Syndrome de Down (extra chromosome 21) ou mongolisme ou trisomie 21.
- Syndrome d'Edward, trisomie du chromosome 18 : la trisomie la plus fréquente après le syndrome de Down.
- Syndrome de Patau, ou syndrome-D ou trisomie 13.
- Syndrome de Jacobsen, ou trouble de délétion 11q terminale (très rare). Plus de détails sur le site http://www.11q.org.
- Syndrome de Klinefelter (XXY).
- Syndrome de Turner (X instead of XX or XY).
- Syndrome XYY
- Syndrome du triple X

Liste complète

[http://www.ornl.gov/hgmis/posters/chromosome/ Affichage graphique détaillé de tous les chromosomes humains et des maladies annotées au bon endroit (en anglais)].

Sources

ja:染色体 ko:염색체

Acide désoxyribo-nucléique

right L'ADN, sigle de acide désoxyribonucléique, est une longue molécule que l'on retrouve dans tous les organismes. L'ADN est présent dans le noyau des cellules eucaryotes, les cellules procaryotes, dans les mitochondries ainsi que dans les chloroplastes. Les organismes vivants les plus simples, les virus, sont constitués essentiellement d'une enveloppe (elle-même constituée de protéines) et d'un brin d'ADN (ou d'ARN). On dit que l'ADN est le support de l'hérédité car cette molécule a la faculté de se reproduire et d'être transmise aux descendants lors des processus de reproduction des organismes vivants. Il est à la base de processus biologiques importants aboutissant à la production des protéines. D'un point de vue chimique, l'ADN est un acide faible.

Structure

processus biologiques Une structure en forme de double hélice (découverte en 1953 par James Dewey Watson, Francis Crick et coll. et en partie grâce aux travaux de Rosalind Franklin). Un polymère de bases désoxyribonucléiques est constitué de répétitions de nucléosides formés d'un groupe phosphate lié à un sucre, le désoxyribose, et à une base azotée A, T, C ou G. Le squelette est formé de la répétition sucre - phosphate, ce qui change est la base.

Bases azotées

Quatre bases ont été identifiées : l’adénine (A) et la guanine (G) font partie de la famille des purines. La thymine (T) et la cytosine (C) sont de la famille des pyrimidines. Elles sont complémentaires entre elles et uniquement associables l’une avec l’autre. Un « brin » d'ADN est formé de la répétition ordonnée de ces quatre bases. pyrimidinepyrimidinepyrimidinepyrimidine

Complémentarité des brins d'ADN

Les deux brins antiparallèles d'ADN sont toujours étroitement reliés entre eux par des liaisons hydrogène (également appelées ponts hydrogène ou encore simplement liaisons H ou ponts H) formées entre les bases complémentaires A-T et G-C. Ces deux brins d'ADN sont dit complémentaires car les purines (Adénine et Guanine) d'un brin font toujours face à des pyrimidines de l'autre brin (Thymine et Cytosine). Les nucléotides sont complémentaires entre eux. Ainsi, l'adénine est complémentaire à la thymine et la guanine est complémentaires à la cytosine. Deux liaisons hydrogène retiennent ensemble la paire A-T et trois retiennent la paire G-C

Propriétés physico-chimiques

Fusion

La température de fusion des acides nucléiques comme l'ADN est la température pour laquelle les deux brins se désapparient. L'énergie thermique apportée devient alors suffisante pour rompre les liaisons H interbrins. Cette température dépend donc de la quantité de liaisons hydrogènes présentes. Plusieurs formules empiriques permettent de calculer la valeur de la temperature de fusion. Elles tiennent compte du pourcentage de base (G+C), de la salinité du milieu ainsi que de divers facteurs correctifs, tels que la presence de structures secondaires intra ou extra moléculaires (repliement de l'ADN sur lui même, formation d'appariements entre deux brins). La connaissance de la temp