Algorithm 2&4: Reporting Set Maximal Matches

Introduction

While Algorithm 3 finds all matches exceeding a fixed threshold \(L\), Algorithm 4 focuses on identifying set maximal matches. A set-maximal match is one among sorted haplotypes that cannot be extended further in either direction (left or right) without encountering a mismatch.

Description

Algorithms 2&4: Reporting set maximal matches

The figure above demonstrates how Algorithm 4 leverages the divergence array (\(d\)) to efficiently control scan boundaries and identify these maximal matches at a specific site \(k\).

Set maximal matches at site \(k\)

At any given site \(k\), our goal is to find the longest matches between a specific haplotype and all other haplotypes in the database.

In the example:

• Current site: \(k = 2\).
• Query haplotype: The haplotype at index 1 in the sorted order (indicated by the green arrow).
• Goal: Identify all longest matches between other haplotypes and the query.

The scanning rules

To find the range of haplotypes that share a maximal match, Algorithm 4 scans upwards and downwards from the query position in the prefix array. The scan is governed by two key rules:

1. Rule 1: Allele block constraint The scan remains within the current allele block. If the query haplotype has a 0 at site \(k\), we only consider other haplotypes that also have a 0 at site \(k\). In the figure, this restricts the scan to positions 0, 1, and 2.
2. Rule 2: Divergence control The scan continues only as long as the divergence values do not increase: \(d[next] \le d[current]\). Since \(d[i]\) represents the site where the match between haplotype \(i\) and \(i-1\) begins, a non-increasing \(d\) ensures the match length is at least as long as the initial match being tracked.

Walking through the example

For the query haplotype at position \(i=1\):

• Divergence values at site \(k=2\): \(d = [3, 2, 1, 3, 0, 1]\).
• Left scan: We examine position 0. Since \(d[0] = 3\) and \(d[1] = 2\) (\(3 > 2\)), Rule 2 is violated, and the scan stops.
• Right scan: We examine position 2. Since \(d[2] = 1\) (\(1 \le 2\)), Rule 2 is satisfied, and the match extends to position 2. If we tried to proceed to position 3, we would encounter a 1 at site \(k\) (violating Rule 1) and \(d[3] = 3\) (violating Rule 2).

The resulting set-maximal match (highlighted in purple) identifies the maximal segment shared with the query haplotype.

Conclusion

• Like the preceding algorithms, Algorithm 4 runs in \(O(MN)\) time. By avoiding the need to iterate through all other haplotypes to identify matches, it remains efficient even for very large datasets.