Arbre PQ
From Wikipedia, the free encyclopedia
En informatique théorique et en bioinformatique, un arbre PQ est une structure de données arborescente qui représente une famille de permutations d'un ensemble fini d'éléments. Cette structure est décrite et appelée ainsi par Kellogg S. Booth et George S. Lueker en 1976[1]. C'est un arbre étiqueté enraciné dans lequel les enfants de chaque nœud sont totalement ordonnés. Chaque élément est représenté par une feuille, et chaque nœud interne est étiqueté par P ou par Q. Un nœud étiqueté P a au moins deux enfants et un nœud Q a au moins trois enfants.
Un arbre PQ représente un ensemble des permutations via les réarrangements autorisés des enfants de ses nœuds : les enfants d'un nœud P peuvent être permutés de manière arbitraire. Les enfants d'un nœud Q peuvent être replacés en ordre inverse, mais ne peuvent pas être réorganisés autrement. Un arbre PQ représente tous les réarrangements de feuilles qui peuvent être obtenus par une séquence quelconque de ces deux opérations. Un arbre PQ qui a de nombreux nœuds P et Q peut représenter des sous-ensembles compliqués de l'ensemble de tous les réarrangements possibles. Cependant, il existe des sous-ensembles de permutations qui ne sont pas représentables de cette manière; en effet, si un arrangement est représenté par un arbre PQ, l'inverse de l'arrangement doit également être représenté par le même arbre.
Les arbres PQ sont utilisés pour résoudre des problèmes où le but est de trouver un ordre qui satisfait diverses contraintes. Dans ces problèmes, les contraintes sur l'ordre sont ajoutées une à la fois, en modifiant la structure arborescente PQ de telle sorte qu'elle ne représente que les commandes satisfaisant la contrainte. Les applications des arbres PQ incluent la création d'une carte de contig à partir de fragments d'ADN[2], les réarrangements[3],[4], les tests sur une matrice pour les propriétés consécutives[1], la reconnaissance des graphes d'intervalle[1] et le test de planarité d'un graphe[1],[5],[6].
