Excap

Excap identifies optimal subsets of genetic markers to maximize discriminatory utility in nonrecombinant sequences such as mitochondrial DNA for forensic and population analyses.

Key Features:

• Depth-First Search and Branch-and-Bound: Employs depth-first search combined with branch-and-bound pruning to explore the space of possible marker sets of a specified size.
• Algorithmic Approach: Handles exponential search complexity by systematically eliminating less promising marker subsets early in the search.
• Data Reduction Techniques: Applies data reduction techniques to simplify datasets and reduce computational demand without significantly compromising accuracy.
• Heuristic for Speedup: Uses a heuristic that trades minimal accuracy for substantial speedup in processing time.

Scientific Applications:

• Forensic mtDNA casework: Applied to forensic mitochondrial DNA casework to optimize marker sets for individual and population discrimination.
• Haplotypic diversity improvement: Optimizes marker selection to achieve improved haplotypic diversity compared with traditional methods.
• Validation on artificial datasets: Validated through evaluations using artificial mtDNA datasets.

Methodology:

Computational methods include depth-first search integrated with branch-and-bound pruning, data reduction techniques, and a heuristic speedup, with systematic elimination of less promising marker subsets to manage exponential search complexity.