Efficient gene orthology inference via large-scale rearrangements

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Previous gene orthology inference relied on genome rearrangements, involving computationally intensive optimal gene matchings via integer linear programming (ILP).
• The optimal capping step in the ILP method exponentially increased the search space, limiting scalability for large or fragmented genomes.

Purpose of the Study:

• To develop a faster and scalable heuristic capping algorithm for gene orthology inference.
• To maintain the accuracy of gene family identification while improving computational performance.

Main Methods:

• Implemented a heuristic capping algorithm that clusters linear genome segments based on gene content intersection.
• Performed independent capping within each cluster, connecting only content-related segments.
• Integrated this heuristic into a pipeline with pre-computed gene similarities and post-processing refinement using the [Formula: see text] algorithm.

Main Results:

• Heuristic capping yielded orthology predictions highly similar to the optimal method for complete primate genomes.
• Enabled efficient analysis of fragmented fruit fly genomes, producing gene families comparable to existing methods.
• The tool identified more complete cliques with higher intersection to known families and improved accuracy through post-processing refinement.

Conclusions:

• The heuristic capping approach offers a significant speed-up in gene orthology inference without compromising accuracy.
• The developed pipeline effectively handles complex and incomplete genome assemblies, enhancing gene family analysis.
• The tool is publicly available, facilitating broader application in genomic research.