Recombination-aware alignment of diploid individuals

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Traditional genome similarity searches use a single string representation, neglecting the complexity of diploid genomes.
• The realistic representation of diploid genomes with two strings has been largely overlooked in similarity search contexts.
• Advancements in sequencing and haplotype assembly are enabling diploid genomes to be represented by pairwise alignments.

Purpose of the Study:

• To propose a generalized global alignment method for measuring similarity between phased diploid genomes.
• To account for mutation, recombination, and potential errors in genome predictions.
• To focus on measuring genome content similarity with free recombination.

Main Methods:

• Generalization of global alignment for phased diploid genomes.
• Development of efficient algorithms for similarity measurement.
• Application of labeled directed acyclic graphs (DAGs) for profile representation in multiple alignments.

Main Results:

• Efficient algorithms for evaluating variation calling predictions.
• Efficient algorithms for progressive multiple alignments using DAGs.
• Demonstration of a generalized approach applicable to complex diploid genome representations.

Conclusions:

• The proposed method offers a more realistic approach to biological similarity search for diploid genomes.
• The algorithms have direct applications in evaluating variation calling and constructing multiple sequence alignments.
• Extensions of the model hold potential for improving phasing algorithms and child genome phasing.