Gene Proximity Analysis across Whole Genomes via PQ Trees 1
- 1 December 2005
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 12 (10) , 1289-1306
Abstract
Permutations on strings representing gene clusters on genomes have been studied earlier by Uno and Yagiura (2000), Heber and Stoye (2001), Bergeron et al. (2002), Eres et al. (2003), and Schmidt and Stoye (2004) and the idea of a maximal permutation pattern was introduced by Eres et al. (2003). In this paper, we present a new tool for representation and detection of gene clusters in multiple genomes, using PQ trees (Booth and Leuker, 1976): this describes the inner structure and the relations between clusters succinctly, aids in filtering meaningful from apparently meaningless clusters, and also gives a natural and meaningful way of visualizing complex clusters. We identify a minimal consensus PQ tree and prove that it is equivalent to a maximal π pattern (Eres et al., 2003) and each subgraph of the PQ tree corresponds to a nonmaximal permutation pattern. We present a general scheme to handle multiplicity in permutations and also give a linear time algorithm to construct the minimal consensus PQ tree. Further, we demonstrate the results on whole genome datasets. In our analysis of the whole genomes of human and rat, we found about 1.5 million common gene clusters but only about 500 minimal consensus PQ trees, with E. Coli K-12 and B. Subtilis genomes, we found only about 450 minimal consensus PQ trees out of about 15,000 gene clusters, and when comparing eight different Chloroplast genomes, we found only 77 minimal consensus PQ trees out of about 6,700 gene clusters. Further, we show specific instances of functionally related genes in two of the cases.Keywords
This publication has 10 references indexed in Scilit:
- Small genome, big insightsNature, 2004
- Tektin3 encodes an evolutionarily conserved putative testicular microtubules‐related protein expressed preferentially in male germ cellsMolecular Reproduction and Development, 2004
- Reversal Distance without Hurdles and Fortresses2004
- Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences2004
- On the Similarity of Sets of Permutations and Its Applications to Genome Comparison2003
- SLAM: Cross-Species Gene Finding and Alignment with a Generalized Pair Hidden Markov ModelGenome Research, 2003
- AVID: A Global Alignment ProgramGenome Research, 2002
- Finding All Common Intervals of k Permutations2001
- Fast Algorithms to Enumerate All Common Intervals of Two PermutationsAlgorithmica, 2000
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976