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 d'éléments, 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 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
Un arbre PQ représente ses 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, tous les arrangements peuvent ne pas être représentables de cette manière; par exemple, 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[réf. nécessaire][5],[6].
Exemples et notation
Si les feuilles d'un arbre PQ sont toutes enfant d'un nœud P, tous les ordres sont possibles. Si les feuilles sont toutes enfant d'un nœud Q, seul l'ordre et son inverse 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és 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]. 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
La notion d'arbre PC, développée par Wei-Kuan Shih et Wen-Lian Hsu[7], est une généralisation de l'arbre PQ. Comme l'arbre PQ, il 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
Notes
- (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
- 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, no 3, , 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, nos 1-2, , 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, , 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, , article no 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, (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, no 10, , 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, , 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, no 1, , p. 54–76 (DOI 10.1016/0022-0000(85)90004-2)
