Indirect identification of horizontal gene transfer

Area of Science:

• Computational Biology
• Evolutionary Biology
• Graph Theory

Background:

• Inferring horizontal gene transfer (HGT) is crucial for understanding genome evolution.
• Existing methods often focus on gene pairs diverging after species divergence, defining later-divergence-time (LDT) graphs.
• Relaxed evolutionary scenarios encompass various duplication-transfer-loss models.

Purpose of the Study:

• To characterize LDT graphs within relaxed evolutionary scenarios.
• To develop polynomial-time algorithms for recognizing LDT graphs and constructing explanatory scenarios.
• To assess the information content of LDT graphs regarding HGT events.

Main Methods:

• Characterizing LDT graphs as a subclass of properly vertex-colored cographs.
• Developing polynomial-time recognition and scenario construction algorithms.
• Simulating evolutionary scenarios with diverse duplication, loss, and HGT events.
• Employing a greedy graph editing scheme to detect implicit HGT events.

Main Results:

• LDT graphs are formally characterized as a specific type of vertex-colored cograph.
• Efficient algorithms for LDT graph recognition and relaxed scenario reconstruction were developed.
• The complete xenology relation is described by rs-Fitch graphs, a class also recognizable in polynomial time.
• Simulations demonstrate that a greedy graph editing approach effectively detects implicit HGT events.

Conclusions:

• LDT graphs provide a robust framework for studying HGT under relaxed evolutionary models.
• Efficient computational tools are now available for analyzing HGT using LDT and rs-Fitch graphs.
• Graph editing schemes offer a practical method for uncovering hidden HGT events from genomic data.