Arbre PQ

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.

Description[modifier | modifier le code]

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].

Exemples et notation[modifier | modifier le code]

Les feuilles sont étiquetées par les éléments à permuter. Si les feuilles d'un arbre PQ sont toutes enfants d'un nœud P, tous les ordres sont possibles. Si les feuilles sont toutes enfants d'un nœud Q, seuls l'ordre de gauche à droite et l'ordre inverse de droite à gauche sont autorisés. Si des nœuds a,b,c sont connectés à un nœud P, qui est connecté à un nœud P racine, toutes les autres feuilles étant connectées directement à la racine, alors tout ordre où a,b,c sont contigus est autorisé.

Lorsqu'une présentation graphique n'est pas disponible, les arbres PQ sont notés à l'aide de listes imbriquées entre parenthèses. Chaque paire de crochets représente un nœud Q et chaque paire de parenthèses arrondies représente un nœud P. Les feuilles sont les éléments non parenthésés. L'arbre représenté ci-contre est équivalent à la liste [1 (2 3 4) 5]. Etudions cet arbre PQ pour voir quel est l'ensemble de permutations correspondant. Pour le fils P, on autorise donc les permutations :

234, 243, 324, 342, 423, 432.

Pour le nœud racine, qui est un noeud Q, on distingue deux :

• Les permutations obtenues où les enfants sont pris dans l'ordre de gauche à droite : 1, puis P puis 5. On concatène 1, avec une permutation pour le fils P puis 5, i.e. on considère les permutations : 12345, 12435, 13245, 13425, 14235, 14325
• Les permutations obtenues où les enfants sont pris dans l'ordre de droite à gauche : 5, puis P puis 1. On considère les permutations : 52341, 52431, 53241, 53421, 54231, 54321.

Pour résumer, cet arbre PQ représente les douze permutations suivantes sur l'ensemble {1, 2, 3, 4, 5} :

12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.

Arbre PC[modifier | modifier le code]

La notion d'arbre PC, développée par Wei-Kuan Shih et Wen-Lian Hsu^[7], est une généralisation de la notion d'arbre PQ. Comme un arbre PQ, un arbre PC représente les permutations par le réarrangement des nœuds d'un arbre, les éléments étant représentés aux feuilles de l'arbre. Contrairement à l'arbre PQ, l'arbre PC n'est pas enraciné. Les nœuds adjacents à un nœud étiqueté P peuvent être réorganisés arbitrairement comme dans l'arbre PQ, tandis que les nœuds adjacents à un nœud étiqueté C ont un ordre cyclique fixe et ne peuvent être réorganisés qu'en inversant cet ordre. Ainsi, un arbre PC ne peut représenter que des ensembles ordonnés clos par permutation circulaire ou inversion d'un arrangement. Cependant, un arbre PQ sur n éléments peut être simulé par un arbre PC sur n + 1 éléments, où l'élément additionnel sert de racine à l'arbre PC. Les opérations de structure de données nécessaires pour exécuter un algorithme de test de planarité sur des arbres PC sont un peu plus simples que les opérations correspondantes sur des arbres PQ.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « PQ tree » (voir la liste des auteurs).

Références[modifier | modifier le code]

• Kellogg S. Booth et George S. Lueker, « Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms », Journal of Computer and System Sciences, vol. 13, n^o 3,‎ 1976, p. 335–379 (DOI 10.1016/S0022-0000(76)80045-1)
• Wei-Kuan Shih et Wen-Lian Hsu, « A new planarity test », Theoretical Computer Science, vol. 223, n^os 1-2,‎ 1999, p. 179–191 (DOI 10.1016/S0304-3975(98)00120-0, lire en ligne)
• Sèverine Bérard, Anne Bergeron, Cédric Chauve et Christophe Paul, « Perfect Sorting by Reversal is not Always Difficult », WABI: Workshop on Algorithms in Bioinformatics,‎ octobre 2005, p. 228-238 (DOI 10.1007/11557067-19, HAL lirmm-00106465)
• Haitao Jiang, Hong Liu, Cédric Chauve et Binhai Zhu, « Breakpoint distance and PQ-trees », Information and Computation, vol. 275,‎ 2020, article n^o 104584 (DOI 10.1016/j.ic.2020.104584)
• Galia R. Zimerman, Dina Svetlitsky, Meirav Zehavi et Michal Ziv-Ukelson, « Approximate Search for Known Gene Clusters in New Genomes Using PQ-Trees », submitted,‎ 2020 (arXiv 2007.03589)
• Gad M. Landau, Laxmi Parida et Oren Weimann, « Gene proximity analysis across wholegenomes via pq trees », Journal of Computational Biology, vol. 12, n^o 10,‎ 2005, p. 1289-1306 (arXiv 2007.03589)
• Bernhard Haeupler et Robert E. Tarjan, « Planarity Algorithms via PQ-Trees (Extended Abstract) », Electronic Notes in Discrete Mathematics, vol. 31,‎ 2008, p. 143–149 (DOI 10.1016/j.endm.2008.06.029).
• Norishige Chiba, Takao Nishizeki, Shigenobu Abe et Takao Ozawa, « A linear algorithm for embedding planar graphs using PQ-trees », Journal of Computer and System Sciences, vol. 30, n^o 1,‎ 1985, p. 54–76 (DOI 10.1016/0022-0000(85)90004-2)

• Portail de l'informatique théorique