Stable (théorie des graphes)thumb|280px|L'ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe. En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. La taille maximum d'un stable d'un graphe, noté I(G), est un invariant du graphe. Il peut être relié à d'autres invariants, par exemple à la taille de l'ensemble dominant maximum, noté dom(G).
Problème du voyageur de commercevignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.
Optimisation linéaire en nombres entiersL'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières.
Microarray analysis techniquesMicroarray analysis techniques are used in interpreting the data generated from experiments on DNA (Gene chip analysis), RNA, and protein microarrays, which allow researchers to investigate the expression state of a large number of genes - in many cases, an organism's entire genome - in a single experiment. Such experiments can generate very large amounts of data, allowing researchers to assess the overall state of a cell or organism. Data in such large quantities is difficult - if not impossible - to analyze without the help of computer programs.
Quantum complexity theoryQuantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes. Two important quantum complexity classes are BQP and QMA.
Analyse en série de l'expression des gènesL'analyse en série de l'expression des gènes (en anglais, Serial Analysis of Gene Expression ou SAGE) est une technique de biologie moléculaire permettant l'analyse de la population en ARNm d'un échantillon donné (organisme, cellules, tissus, etc.). La méthode originelle a été mise au point, et publiée en 1995, par le du centre d'oncologie de l'université Johns-Hopkins. La méthode SAGE est basée sur l'isolation de séquences spécifiques (étiquettes) de chaque ARN, la production des ADN complémentaires (ADNc) correspondant, la production d'une molécule d'ADN synthétique comportant tous ces ADNc, puis le séquençage de cette molécule.
Optimisation linéairethumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.
Gene expression profilingIn the field of molecular biology, gene expression profiling is the measurement of the activity (the expression) of thousands of genes at once, to create a global picture of cellular function. These profiles can, for example, distinguish between cells that are actively dividing, or show how the cells react to a particular treatment. Many experiments of this sort measure an entire genome simultaneously, that is, every gene present in a particular cell. Several transcriptomics technologies can be used to generate the necessary data to analyse.
Ensemble dominantEn théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donné G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.
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).
