GénomeLe génome (//), ou plus rarement génôme, est l'ensemble du matériel génétique d'une espèce codé dans son acide désoxyribonucléique (ADN), à l'exception de certains virus dont le génome est constitué d'acide ribonucléique (ARN). Il contient en particulier tous les gènes codant des protéines ou correspondant à des ARN structurés. Il se décompose donc en séquences codantes (transcrites en ARN messagers et traduites en protéines) et non codantes (non transcrites, ou transcrites en ARN, mais non traduites).
Biologie de l'évolutionEvolutionary biology is the subfield of biology that studies the evolutionary processes (natural selection, common descent, speciation) that produced the diversity of life on Earth. It is also defined as the study of the history of life forms on Earth. Evolution holds that all species are related and gradually change over generations. In a population, the genetic variations affect the phenotypes (physical characteristics) of an organism. These changes in the phenotypes will be an advantage to some organisms, which will then be passed onto their offspring.
Distance d'édition sur les arbresEn informatique théorique, en biochimie et aussi dans des applications, en vision par ordinateur par exemple, la distance d'édition d'arbres (en anglais tree edit distance) est une mesure qui évalue, en termes de nombre de transformations élémentaires, le nombre d'opérations nécessaires et leur coût pour passer d'un arbre à un autre. C'est une notion qui étend, aux arbres, la distance d'édition (ou distance de Levenshtein) entre chaînes de caractères.
Réduction polynomialeUne réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP. Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage est réductible en temps polynomial à un langage (noté ) s'il existe une fonction calculable en temps polynomial telle que pour tout , si et seulement si .
Hiérarchie polynomialeEn théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale. On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel ().
Complexité en tempsEn algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
Signature d'une permutationEn mathématiques, une permutation de support fini est dite paire si elle présente un nombre pair d'inversions, impaire sinon. La signature d'une permutation vaut 1 si celle-ci est paire, –1 si elle est impaire. L'application signature, du groupe symétrique dans le groupe ({–1, 1}, ×), est un morphisme, c'est-à-dire qu'elle vérifie une propriété analogue à la règle des signes. Toute permutation se décompose en un produit de transpositions.
Histoire de la pensée évolutionnisteLe concept de pensée évolutionniste, selon lequel les espèces évoluent au cours du temps, remonte à l'Antiquité, dans les idées des Grecs, des Romains, des Chinois, de même que dans la science islamique du Moyen Âge. Cependant, jusqu'au , la pensée biologique occidentale était dominée par l'essentialisme selon lequel les espèces possédaient des caractéristiques inaltérables. Cette vision changea lors du siècle des Lumières lorsque la vision mécanique se développa dans les sciences naturelles à partir des sciences physiques.
Schéma d'approximation en temps polynomialEn informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS.
