Merging Partially Labelled Trees: Hardness and a Declarative Programming Solution

Area of Science:

• Population genetics
• Computational biology
• Phylogenetics

Background:

• Haplotype networks are crucial for representing intraspecific gene evolution.
• Existing methods for network reconstruction face computational challenges.
• The problem of finding a minimum common supergraph of partially labeled trees is complex.

Purpose of the Study:

• To investigate the computational complexity of reconstructing haplotype networks.
• To develop practical computational approaches for network reconstruction.
• To assess the performance of novel reconstruction methods.

Main Methods:

• We analyze the complexity of the minimum common supergraph problem for t=3 partially labeled trees.
• A declarative programming approach using the idpsystem is proposed for optimal solutions.
• A heuristic approach based on the idpsystem is also developed.

Main Results:

• The decision problem for minimum common supergraph of 3 partially labeled trees is NP-complete.
• Both declarative and heuristic methods were implemented using the idpsystem.
• Performance was evaluated on randomly generated datasets.

Conclusions:

• The NP-completeness result highlights the inherent difficulty of this network reconstruction problem.
• The proposed idpsystem-based approaches offer practical solutions for haplotype network reconstruction.
• Further research can explore these methods on diverse biological datasets.