founder sequences

founder sequences reconstructs a minimal set of founder sequences from aligned haplotype sequences by partitioning haplotypes into segments that preserve contiguities for downstream pan-genomic analyses such as read alignment and variant calling.

Key Features:

• Segmentation and founder sequence reconstruction: Partitions haplotype sequences into disjoint segments with a minimum length threshold L and identifies founder blocks by minimizing the number of distinct substrings within each segment, which are concatenated to form founder sequences.
• Minimum-segmentation optimization: Solves the minimum segmentation problem using a polynomial-time algorithm despite the NP-hardness of optimizing the overall founder set.
• Algorithmic complexity and scalability: Implements an O(mn) time algorithm, improving on prior O(mn^2) approaches, to enable processing of large datasets such as thousands of complete human chromosomes.

Scientific Applications:

• Pan-genome representation: Produces compact founder-sequence representations of large aligned haplotype collections for pan-genomic analyses.
• Genetic diversity and evolutionary analysis: Enables study of genetic diversity and evolutionary patterns by preserving contiguous haplotype structure in a reduced sequence set.
• Downstream variant analysis: Supports scalable read alignment and variant calling workflows by reducing the complexity of input haplotype data.

Methodology:

Partition haplotype sequences into disjoint segments with minimum length L; optimize segmentation to minimize the number of distinct substrings per segment and identify founder blocks to concatenate into founder sequences; employ a polynomial-time algorithm for the minimum segmentation problem with an O(mn) time implementation (improving over O(mn^2)).