Comparing pedigree graphs

Area of Science:

• Computational Biology
• Bioinformatics
• Graph Theory

Background:

• Traditional pedigree construction relies on costly genealogical record examination.
• Automated methods reconstruct ancestral individuals from extant genetic data.
• Evaluating automated pedigree reconstruction requires comparing estimated to true pedigrees.

Purpose of the Study:

• To develop and analyze algorithms for comparing estimated pedigrees to true pedigrees.
• To address the pedigree isomorphism and pedigree edit distance problems.
• To assess the computational complexity of pedigree comparison.

Main Methods:

• Developed a linear-time algorithm for the leaf-labeled pedigree isomorphism problem.
• Presented exact and heuristic algorithms for the pedigree edit distance problem.
• Proved hardness results for pedigree isomorphism (as hard as graph isomorphism) and edit distance (APX-hard, NP-hard).

Main Results:

• A linear-time algorithm for leaf-labeled pedigree isomorphism.
• Multiple algorithms for pedigree edit distance, including fast exact and general heuristic approaches.
• Demonstrated the computational hardness of pedigree comparison problems.

Conclusions:

• The study provides efficient algorithms and complexity insights for pedigree comparison.
• These methods are crucial for evaluating automated pedigree reconstruction from genetic data.
• The findings advance the field of computational phylogenetics and bioinformatics.