Gene Proximity Analysis across Whole Genomes via PQ Trees1
Gene Proximity Analysis across Whole Genomes via PQ Trees1
复制标题
通过 PQ 树进行全基因组基因邻近分析1
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Oren Weimann
中科院分区：
文献类型：
--
作者：
G. M. Landau;L. Parida;Oren Weimann
Uno和Yagiura（2000），Heber and Stoye（2001），Bergeron等人早先研究了代表基因组基因簇的字符串排列。 （2002），Eres等。 （2003）以及Schmidt和Stoye（2004）以及Eres等人引入了最大置换模式的想法。 （2003）。在本文中，我们提出了一种使用PQ树来表示和检测多个基因组中基因簇的新工具（Booth and Leuker，1976）：这描述了簇的内在结构和簇之间的关系，有助于从显然毫无意义的毫无意义地过滤有意义集群，还提供了一种自然而有意义的方式，可视化复杂的簇。我们确定了最小的共识PQ树，并证明它等效于最大PI模式（Eres等，2003），PQ树的每个子图都对应于非最大置换模式。我们提出了一个一般方案，以处理排列中的多重性，并给出线性时间算法以构建最小共识PQ树。此外，我们证明了整个基因组数据集的结果。在我们对人和大鼠的整个基因组的分析中，我们发现了约150万个普通基因簇，但只有大约500个最低共识PQ树，具有大肠杆菌K-12和枯草芽孢杆菌基因组，我们只发现了约450个最小共识PQ大约15,000个基因簇中的树木，在比较八个不同的叶绿体基因组时，我们发现只有77种最小的共识PQ树。 6,700个基因簇。此外，我们在两种情况下显示了功能相关基因的特定实例。
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 pi 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.