Matching algorithms for assigning orthologs after genome duplication events

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Whole-genome duplications complicate the identification of orthologous genes.
• Existing methods may not fully account for the complexities of duplicated genomes.

Purpose of the Study:

• To introduce and analyze novel graph-based models for ortholog assignment in genomes with whole-genome duplications.
• To develop efficient algorithms for these models, considering a 'duplication bonus' parameter.

Main Methods:

• Development of two graph-based models for ortholog assignment.
• Algorithmic analysis, including polynomial-time solvability and NP-hardness.
• Design of fixed-parameter algorithms for the NP-hard model.
• Experimental evaluation on plant genome datasets.

Main Results:

• The first model is polynomial-time solvable; the second is NP-hard but addressed with fixed-parameter algorithms.
• The NP-hard model offers improved cluster quality over coverage.
• Biologically significant ortholog predictions are achievable with appropriate parameter tuning.

Conclusions:

• The proposed graph-based models and algorithms provide effective tools for ortholog assignment in duplicated genomes.
• The 'duplication bonus' parameter is crucial for balancing prediction quality and coverage.
• The methods demonstrate potential for biologically meaningful ortholog discovery in plant genomics.