PQ tree
Encyclopedia
A PQ tree is a tree-based data structure
that represents a family of permutation
s on a set of elements, discovered and named by Kellogg S. Booth and George S. Lueker in 1976. It is a rooted, labeled tree, in which each element is represented by one of the leaf nodes, and each non-leaf node is labelled P or Q. A P node has at least two children, and a Q node has at least three children.
A PQ tree represents its permutations via permissible reorderings of the children of its nodes. The children of a P node may be reordered in any way. The children of a Q node may be put in reverse order, but may not otherwise be reordered. A PQ tree represents all leaf node orderings that can be achieved by any sequence of these two operations. A PQ tree with many P and Q nodes can represent complicated subsets of the set of all possible orderings. However, not every set of orderings may be representable in this way; for instance, if an ordering is represented by a PQ tree, the reverse of the ordering must also be represented by the same tree.
PQ trees are used to solve problems where the goal is to find an ordering that satisfies various constraints. In these problems, constraints on the ordering are included one at a time, by modifying the PQ tree structure in such a way that it represents only orderings satisfying the constraint. Applications of PQ trees include creating a contig map
from DNA
fragments, testing a matrix for the consecutive ones property, recognizing interval graph
s and determining whether a graph is planar
.
Where graphical presentation is unavailable PQ trees are often noted using nested parenthesized lists. Square parentheses represents a Q node and regular ones represents P nodes. Leaves are non-parentheses elements of the lists. The image on the left is represented in this notation by [1 (2 3 4) 5]. This PQ tree represents the following twelve permutations on the set {1, 2, 3, 4, 5}:
algorithm on PC trees are somewhat simpler than the corresponding operations on PQ trees.
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
that represents a family of permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s on a set of elements, discovered and named by Kellogg S. Booth and George S. Lueker in 1976. It is a rooted, labeled tree, in which each element is represented by one of the leaf nodes, and each non-leaf node is labelled P or Q. A P node has at least two children, and a Q node has at least three children.
A PQ tree represents its permutations via permissible reorderings of the children of its nodes. The children of a P node may be reordered in any way. The children of a Q node may be put in reverse order, but may not otherwise be reordered. A PQ tree represents all leaf node orderings that can be achieved by any sequence of these two operations. A PQ tree with many P and Q nodes can represent complicated subsets of the set of all possible orderings. However, not every set of orderings may be representable in this way; for instance, if an ordering is represented by a PQ tree, the reverse of the ordering must also be represented by the same tree.
PQ trees are used to solve problems where the goal is to find an ordering that satisfies various constraints. In these problems, constraints on the ordering are included one at a time, by modifying the PQ tree structure in such a way that it represents only orderings satisfying the constraint. Applications of PQ trees include creating a contig map
Contig
A contig is a set of overlapping DNA segments that together represent a consensus region of DNA. In bottom-up sequencing projects, a contig refers to overlapping sequence data ; in top-down sequencing projects, contig refers to the overlapping clones that form a physical map of the genome that is...
from DNA
DNA
Deoxyribonucleic acid is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms . The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in...
fragments, testing a matrix for the consecutive ones property, recognizing interval graph
Interval graph
In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
s and determining whether a graph is planar
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
.
Examples and notation
If all the leaves of a PQ tree are connected directly to a root P node then all possible orderings are allowed. If all the leaves are connected directly to a root Q node then only one order (and its reverse) is allowed. If nodes a,b,c connect to a P node, which connects to a root P node, with all other leaf nodes connected directly to the root, then any ordering where a,b,c are contiguous is allowed.Where graphical presentation is unavailable PQ trees are often noted using nested parenthesized lists. Square parentheses represents a Q node and regular ones represents P nodes. Leaves are non-parentheses elements of the lists. The image on the left is represented in this notation by [1 (2 3 4) 5]. This PQ tree represents the following twelve permutations on the set {1, 2, 3, 4, 5}:
- 12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.
PC trees
The PC tree, developed by Wei-Kuan Shih and Wen-Lian Hsu, is a more recent generalization of the PQ tree. Like the PQ tree it represents permutations by reorderings of nodes in a tree, with elements represented at the leaves of the tree. Unlike the PQ tree, the PC tree is unrooted. The nodes adjacent to any non-leaf node labeled P may be reordered arbitrarily as in the PQ tree, while the nodes adjacent to any non-leaf node labeled C have a fixed cyclic order and may only be reordered by reversing this order. Thus, a PC tree can only represent sets of orderings in which any circular permutation or reversal of an ordering in the set is also in the set. However, a PQ tree on n elements may be simulated by a PC tree on n + 1 elements, where the extra element serves to root the PC tree. The data structure operations required to perform a planarity testingPlanarity testing
In graph theory, the planarity testing problem asks whether, given a graph, that graph is a planar graph . This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures...
algorithm on PC trees are somewhat simpler than the corresponding operations on PQ trees.