SLAB: A Sweep Line Algorithm in PBWT for Finding Haplotype Block Cores

This paper introduces SLAB, an efficient sweep line algorithm based on PBWT that identifies width-maximal haplotype block cores to reveal population genetic insights and selection signals complementary to traditional IBD rate analyses.

The Gist

The Big Picture: Finding the "Heart" of Shared DNA

Imagine you have a massive library containing the genetic "cookbooks" of nearly one million people (the UK Biobank). Each cookbook is a long list of instructions (DNA) written in a code of four letters (A, C, G, T).

Scientists know that people often share chunks of these instructions because they share ancestors. These shared chunks are called haplotype blocks. Think of them like stamps on a letter. If you and your cousin both have the same rare stamp on your letter, it means you likely got that letter from the same great-grandparent.

The Problem:
When you look at a million people, you don't just find simple pairs of cousins. You find huge, messy groups of people sharing different parts of the same stamp.

• Group A shares a stamp from position 1 to 10.
• Group B shares a stamp from position 5 to 15.
• Group C shares a stamp from position 8 to 20.

These groups overlap in confusing ways. Some overlaps are small (just two people), while others are massive (thousands of people). The researchers wanted to find the "Block Cores."

The Analogy:
Imagine a crowded room where everyone is holding a long strip of colored tape.

• Some strips are red, some are blue.
• The strips overlap on the floor.
• In some spots, only two strips cross.
• In other spots, a huge pile of 50 strips is all stacked on top of each other.

The "Block Core" is that specific spot on the floor where the maximum number of strips are stacked directly on top of one another. It's the "heart" of the overlap. Finding this heart tells us where the most significant shared ancestry or evolutionary event happened.

---

The Challenge: The Needle in a Haystack (But the Haystack is Moving)

Finding these "stacks" is incredibly hard. If you have 1 million people, the number of possible combinations is astronomical. It's like trying to find the exact moment in a 24-hour movie where the most people in the audience are holding up their hands at the same time, but the movie is 100,000 frames long, and the "hands" (DNA segments) start and stop at random times.

Traditional methods are too slow. They try to check every single pair of people against every other pair. This would take centuries.

The Solution: The "Sweep Line" Algorithm (SLAB)

The authors created a new tool called SLAB (Sweep Line Algorithm in PBWT). Here is how it works, using a metaphor:

The Metaphor: The Moving Spotlight
Imagine a giant, horizontal laser beam (the "Sweep Line") moving slowly from the left side of a stage to the right side.

• On the stage, there are thousands of people (haplotypes) holding up signs (DNA blocks) that say "I am here from mile 10 to mile 20."
• As the laser beam moves, it lights up the people currently standing in its path.
• The Trick: Instead of looking at everyone, the algorithm uses a special sorting trick (called PBWT) that organizes the people on stage so that those holding similar signs are standing right next to each other in a line.

How SLAB finds the "Core":

1. The Start: When the laser hits the start of a sign, it adds that person to its "active list."
2. The Scan: As the laser moves, it checks the "active list." Because the people are sorted by their DNA patterns, the algorithm can instantly see: "Hey, look at this group of 500 people standing right next to each other in the line. They all have a sign that covers this exact spot."
3. The End: When the laser hits the end of a sign, it removes that person from the list.
4. The Discovery: By doing this sweep, the computer instantly spots the "stacks" (the cores) where the most signs overlap, without having to check every single person against every other person.

It's like using a metal detector that is so smart it only beeps when it finds a pile of gold coins, ignoring the single loose coin here and there.

What Did They Find? (The Results)

When the researchers ran this algorithm on the UK Biobank data, they found some fascinating "hearts" of shared DNA:

1. The Immune System (Chromosome 6): They found the biggest "stack" of shared DNA in the part of the genome that controls our immune system (the MHC region). This makes sense because our immune systems need to be diverse, but certain ancient defenses are shared by huge groups of people.
2. The Neanderthal Connection (Chromosome 3): They found a massive overlap in a gene called SLC6A20. This gene is linked to severe COVID-19. The "stack" here is made up of DNA that humans inherited from Neanderthals thousands of years ago. The algorithm showed that while many people have this Neanderthal DNA, the specific "core" group is distinct.
3. Lactose Tolerance (Chromosome 2): They found a spot where many people share DNA related to digesting milk (lactose). This is a classic sign of natural selection: humans who could drink milk survived better, so their DNA spread like wildfire, creating a huge "stack" of shared blocks.

Why Does This Matter?

1. It's Faster:
Before this, analyzing this much data would take a supercomputer weeks. SLAB does it in hours. It's like switching from counting grains of sand one by one to using a sieve.

2. It Finds Hidden Patterns:
Old methods looked at how many people share any DNA (IBD rates). But SLAB looks at the structure of the sharing.

• Analogy: Imagine a party. Old methods count how many people are wearing red hats. SLAB looks for the specific group of people wearing red hats and blue shoes and holding a specific drink. It finds the "cliques" that matter most.

3. It Helps Find Disease Genes:
By pinpointing exactly where these "stacks" of shared DNA are, scientists can narrow down the search for genes that cause diseases. If a "stack" of shared DNA is found in people with a specific disease, that spot on the DNA is a prime suspect.

Summary

The paper introduces SLAB, a super-fast, smart way to find the "center of gravity" in shared human DNA. By using a moving laser beam (Sweep Line) and a clever sorting trick (PBWT), it can sift through millions of genetic profiles to find the most important shared chunks. This helps us understand our evolutionary history (like Neanderthal DNA) and find the genetic roots of modern diseases.

Technical Summary

1. Problem Statement

With the proliferation of large-scale biobank datasets (e.g., UK Biobank) and high-quality phased haplotype data, researchers can identify complex patterns of haplotype sharing. While traditional methods focus on pairwise Identical-by-Descent (IBD) segments or identifying individual haplotype blocks (contiguous regions shared by multiple individuals), these approaches often fail to capture the structural complexity of overlapping blocks.

• The Gap: Direct application of existing block-finding algorithms results in numerous overlapping blocks. While these overlaps might seem redundant, their specific patterns (e.g., layered structures where smaller blocks are preserved across broader sets of haplotypes) contain critical information about population structure, relatedness, and evolutionary processes like natural selection.
• The Challenge: Defining and efficiently computing the "core" of these overlapping structures is computationally difficult. The problem of finding the largest set of mutually overlapping blocks is analogous to the Maximum Clique Problem, which is generally NP-hard. However, the genomic ordering of haplotypes offers structural constraints that could be exploited for efficiency.

2. Methodology: The SLAB Framework

The authors propose SLAB (Sweep Line Algorithm in PBWT), a framework designed to identify Haplotype Block Cores.

2.1 Definitions and Graph Construction

• Haplotype Block: A tuple $(H, s, e)$ representing a set of haplotypes $H$ sharing a sequence from site $s$ to $e$. The paper focuses on width-maximal blocks (cannot add more haplotypes without violating length constraints).
• Block Overlap Graph: A graph where nodes are haplotype blocks. An edge exists between two blocks if they satisfy user-defined thresholds for genomic overlap length ($L$) and shared haplotype count ($W$).
• Block Core (Maximum Clique): The largest subset of blocks within a connected component that all mutually overlap. This represents the region with the maximum number of overlapping blocks.
• Local Core (Maximal Clique): A subset of blocks that mutually overlap but cannot be extended; these may not be the largest in the component but represent stable local structures.
• Local IBD Graph (LIG): The authors map block overlaps to Local IBD graphs, where a "W-clique" at a specific site represents $W$ haplotypes sharing IBD. A block core corresponds to a persistent clique across a genomic interval.

2.2 The Sweep Line Algorithm

To solve the Maximum Clique problem efficiently within the context of genomic data, the authors leverage the Positional Burrows-Wheeler Transform (PBWT).

• PBWT Properties: PBWT sorts haplotypes based on their reversed prefix order. Crucially, within a matching block, the relative order (rank) of haplotypes in the PBWT matrix remains invariant.
• 2D Sweep Line Approach:
  1. Events: Each block generates two events: a start ($s$) and an end ($e$).
  2. Sorting: Events are sorted by genomic position.
  3. Active Set: As the sweep line moves, blocks are added to an "active set" when they start and removed when they end.
  4. Rank Projection: At each "end" event, the haplotypes of all currently active blocks are projected onto the PBWT rank array (inverse Positional Prefix Array). Because of the PBWT property, matching haplotypes form contiguous intervals in the rank space.
  5. Interval Intersection: The algorithm identifies the intersection of these rank intervals. The size of the intersection corresponds to the number of mutually overlapping haplotypes.
  6. Complexity: By exploiting the sorted nature of PBWT and the contiguous intervals, the algorithm achieves a time complexity of $O(B \log B + B \cdot a \cdot i \log i)$, where $B$ is the number of blocks, $a$ is the max active blocks, and $i$ is the number of rank intervals. This is significantly faster than general clique-finding algorithms.

2.3 Implementation Details

• Input: Phased haplotype panels (e.g., from UK Biobank).
• Preprocessing: Uses P-smoother for error correction and c-PBWT to detect initial width-maximal blocks.
• Core Detection: Iterates through connected components of the overlap graph to find maximum cliques (cores) and maximal cliques (local cores).

3. Key Contributions

1. Definition of Block Cores: Formalized the concept of "block cores" as the maximum clique of overlapping haplotype blocks, distinguishing them from simple pairwise IBD or isolated blocks.
2. Efficient Algorithm (SLAB): Developed a polynomial-time sweep line algorithm tailored for genomic data using PBWT rank properties, making the NP-hard Maximum Clique problem tractable for biobank-scale data (nearly 1 million haplotypes).
3. Local IBD Graph Sequence (LIGS): Introduced a framework linking block overlaps to Local IBD graphs, providing a coherent view of shared ancestry across contiguous genomic sites.
4. Scalability: Demonstrated the ability to process the entire UK Biobank dataset (autosomes) in a reasonable timeframe (hours) on standard high-performance hardware.

4. Results and Applications

The authors applied SLAB to the UK Biobank dataset (phased data, ~1M haplotypes).

• Performance:
  • Processing all autosomes for 2 cM blocks took ~4 hours; 1 cM blocks took ~32 hours (due to a higher number of blocks).
  • Memory usage peaked at 278 GB for Chromosome 1.
• Biological Insights:
  • Chromosome 6 (MHC Region): Identified the largest clique (980 blocks) in the Extended Major Histocompatibility Complex (xMHC), a region known for high diversity and selection.
  • Chromosome 3 (Neanderthal Introgression): Found a large clique overlapping the SLC6A20 gene. This region contains variants associated with severe COVID-19 risk, derived from Neanderthal introgression.
    • Key Finding: While the clique size was large, the intersection of samples (individuals carrying the risk haplotype) was small compared to the union. This suggests the core captures a specific, perhaps population-specific, selection signal that standard IBD rate analysis might miss.
  • Chromosome 2 (LCT Gene): The maximum clique coincided with a peak in IBD rates near the LCT gene (lactose tolerance), validating the method against known selection signals.
• Comparison with IBD Rates:
  • SLAB results were consistent with IBD rate analysis in some regions (e.g., LCT) but revealed complementary information in others (e.g., Chromosome 3).
  • Unlike IBD rates which measure pairwise sharing, block cores capture multi-way sharing and layered structures, revealing signals of selection that are not captured by pairwise metrics alone.
• Population Structure: Analysis of a specific clique on Chromosome 2 revealed distinct ethnic compositions (e.g., high Ashkenazi Jewish representation in the intersection vs. British in the union), demonstrating the method's utility in detecting population-specific haplotype structures.

5. Significance

• Novelty in Population Genetics: SLAB moves beyond pairwise IBD to analyze multi-way haplotype sharing, offering a more granular view of evolutionary history and selection.
• Computational Efficiency: By adapting the sweep line algorithm to the PBWT structure, the authors solved a theoretically hard problem efficiently enough for biobank-scale analysis.
• Biological Utility: The method successfully identified known selection signals (MHC, LCT) and uncovered new insights into Neanderthal-derived risk factors (Chromosome 3) that were not fully captured by traditional IBD rate metrics.
• Future Applications: The framework is applicable to Genome-Wide Association Studies (GWAS) for localizing causal variants, detecting recombination hotspots, and refining population structure analysis.

In summary, SLAB provides a robust, scalable, and theoretically grounded method for dissecting the complex architecture of shared haplotype blocks, bridging the gap between computational efficiency and deep biological insight in large-scale genomic studies.