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

Area of Science:

• Comparative genomics
• Bioinformatics
• Computational biology

Background:

• Gene clusters are conserved across genomes, aiding gene annotation and evolutionary studies.
• Identifying known gene clusters in new genomic sequences is crucial due to rapid genome sequencing.
• Existing methods face challenges with gene order variations and substitutions.

Purpose of the Study:

• To define and address the PQ-TREE SEARCH problem for identifying approximate gene cluster instances in new genomic sequences.
• To develop an efficient algorithm and tool (PQFinder) for this task.
• To analyze the presence and rearrangements of chromosomal gene clusters in prokaryotic plasmids.

Main Methods:

• Defined the PQ-TREE SEARCH problem, incorporating gene order constraints, substitutions, deletions, and insertions.
• Developed a parameterized algorithm with a runtime of O(2^k * poly(n)), where k is the maximum node degree in the PQ-tree.
• Implemented the algorithm as the PQFinder search tool.

Main Results:

• PQFinder was applied to 1,487 prokaryotic genomes, searching for chromosomal gene clusters within plasmids.
• Identified 29 instances of chromosomal gene clusters exhibiting rearrangements guided by PQ-trees.
• Detailed analysis of a heavy metal efflux pump gene cluster revealed novel structural variants.

Conclusions:

• PQFinder is an effective tool for discovering rearranged gene clusters, particularly chromosomal clusters found in plasmids.
• The findings highlight the dynamic nature of gene cluster organization and evolution across different genomic contexts.
• This approach facilitates the identification of new functional variants and evolutionary insights from genomic data.