Approximate search for known gene clusters in new genomes using PQ-trees

Galia R. Zimerman, Dina Svetlitsky, Meirav Zehavi, Michal Ziv-Ukelson

TL;DR

Researchers have developed PQFinder, a tool that uses a specialized data structure called a PQ-tree to search for known gene clusters in new genomes. Unlike traditional search methods, this approach handles complex genomic rearrangements, gene substitutions, and "noisy" data (insertions/deletions), providing a flexible way to identify functionally related groups of genes across different genetic contexts.

What Problem Does This Paper Address?

In prokaryotes, genes that work together (like those in an operon) are often physically clustered. Finding these gene clusters helps scientists infer the function of unknown genes. However, evolution is messy: clusters can be rearranged (inverted or transposed), genes can be swapped for functional equivalents, and some genes might be missing or extra.

Existing tools often struggle with this "approximate" nature of gene clusters. The authors address the challenge of taking a known gene cluster—represented by a set of observed gene orders—and searching for its "approximate" instances in a new genome, specifically looking for chromosomal clusters that have migrated and rearranged within plasmids.

Methods

The core of the paper is the PQ-Tree Search problem.

  • PQ-Trees: This data structure represents a set of permutations. P-nodes allow their children to appear in any order, while Q-nodes require children to appear in a specific (or reversed) order. This acts as a "grammatical model" for allowed biological rearrangements.
  • The Algorithm: The authors prove that searching for a PQ-tree in a genome is NP-hard. To solve it, they developed a Fixed-Parameter Tractable (FPT) algorithm using dynamic programming. The complexity is $O^*(2^\gamma)$, where $\gamma$ is the maximum degree of a node in the tree. This makes it efficient for typical biological clusters where $\gamma$ is small.
  • Scoring: The search isn't just binary; it uses a scoring function that combines sequence homology (how similar the DNA is) with semantic similarity (how similar the functional descriptions of the genes are) to handle gene substitutions.
  • PQFinder: The algorithm is implemented as an open-source tool available on GitHub.

Datasets

The researchers evaluated their tool using:

  • 1,487 prokaryotic genomes downloaded from GenBank.
  • 933 plasmids found within those genomes.
  • 26,270 initial gene clusters generated using the CSBFinder-S tool to serve as the "known" queries.

Key Insights and Ideas

  • PQ-trees as Constraints: Instead of allowing any rearrangement, the PQ-tree restricts the search to rearrangements actually observed in nature, which increases search specificity.
  • Bridging Chromosomes and Plasmids: The study focuses on finding chromosomal gene clusters that have "jumped" to plasmids. Because plasmids evolve faster and are sequenced more "noisily," an approximate search tool like PQFinder is uniquely suited for this task.
  • Semantic Scoring: By using Natural Language Processing (NLP) on gene annotations, the tool can recognize that two genes are "equivalent" even if their sequences have diverged significantly, as long as their functional descriptions remain similar.

Key Results

  • Discovery: PQFinder identified 29 chromosomal gene clusters that appeared in rearranged forms within plasmids.
  • Functional Trends: Most of these clusters (21 out of 29) were related to transporters, including ABC-type transport systems and efflux pumps.
  • Case Study: They highlighted a heavy metal efflux pump in Cupriavidus metallidurans CH34. PQFinder found a variant in a plasmid that was missing a specific outer-membrane protein but remained functional, likely as a defense mechanism against heavy metal stress in polluted environments.
  • Performance: The tool is practical; running 779 PQ-trees against 933 plasmids took about 1 hour and 47 minutes on standard server hardware.

Limitations and Future Work

  • Specificity vs. Sensitivity: If a PQ-tree is built from very rare gene orders, it can become too "loose," allowing too many rearrangements and lowering the search specificity.
  • Stochastic Modeling: The authors suggest that future versions could use a "stochastic PQ-tree," where internal nodes hold probabilities for specific rearrangements.
  • Complex Events: The current model doesn't explicitly handle gene duplications, merges, or splits—common events in cluster evolution that the authors hope to address in future iterations.

Reference: Zimerman, G. R., et al. (2020). Approximate Search for Known Gene Clusters in New Genomes Using PQ-Trees. arXiv:2007.03589v1 [q-bio.GN].

Summary updated

Abstract

Gene clusters are groups of genes that are co-locally conserved across various genomes, not necessarily in the same order. Their discovery and analysis is valuable in tasks such as gene annotation and prediction of gene interactions, and in the study of genome organization and evolution. The discovery of conserved gene clusters in a given set of genomes is a well studied problem, but with the rapid sequencing of prokaryotic genomes a new problem is inspired. Namely, given an already known gene cluster that was discovered and studied in one genomic dataset, to identify all the instances of the gene cluster in a given new genomic sequence. Thus, we define a new problem in comparative genomics, denoted PQ-Tree Search that takes as input a PQ-tree T representing the known gene orders of a gene cluster of interest, a gene-to-gene substitution scoring function h, integer arguments $$d_T$$ and $$d_S$$ , and a new sequence of genes S. The objective is to identify in S approximate new instances of the gene cluster; These instances could vary from the known gene orders by genome rearrangements that are constrained by T, by gene substitutions that are governed by h, and by gene deletions and insertions that are bounded from above by $$d_T$$ and $$d_S$$ , respectively. We prove that PQ-Tree Search is NP-hard and propose a parameterized algorithm that solves the optimization variant of PQ-Tree Search in $$O^*(2^{\gamma })$$ time, where $$\gamma$$ is the maximum degree of a node in T and $$O^*$$ is used to hide factors polynomial in the input size. The algorithm is implemented as a search tool, denoted PQFinder, and applied to search for instances of chromosomal gene clusters in plasmids, within a dataset of 1,487 prokaryotic genomes. We report on 29 chromosomal gene clusters that are rearranged in plasmids, where the rearrangements are guided by the corresponding PQ-trees. One of these results, coding for a heavy metal efflux pump, is further analysed to exemplify how PQFinder can be harnessed to reveal interesting new structural variants of known gene clusters.
BibTeX
@article{zimerman2021approximate,
  author = {Galia R. Zimerman and Dina Svetlitsky and Meirav Zehavi and Michal Ziv-Ukelson},
  title = {{Approximate search for known gene clusters in new genomes using PQ-trees}},
  journal = {Algorithms Mol. Biol.},
  year = {2021},
  doi = {10.1186/s13015-021-00190-9},
}

Loading related content...

Figure