Scheduling Straggler Windows in Streaming Haplotype Phasing

A long-read sequencer produces reads continuously for hours. Clinicians often need a small number of answers early, for example whether two variants in a disease gene sit on the same parental chromosome. Yet phasing tools, which work out which alleles came from the mother and which from the father, wait for the whole run to finish and then process everything in one batch. This proposal treats phasing as an online scheduling problem. Genomic windows become jobs. Each job becomes available once enough reads cover it, takes a hard-to-predict amount of solver time, and carries a clinical weight. The goal is to minimize the weighted average time until each window's phase is reported. We do this without making phasing less accurate than the batch pipeline.

The specific bet is that latency in this setting comes mostly from "straggler" windows. These are regions of very high depth or near-identical parental chromosomes, where the underlying error-correction problem becomes expensive and a solver can stall. Scheduling theory says such stragglers call for preemption, meaning pausing a job, and migration, meaning resuming it on another worker. This is not a matter of taste: for general sum-of-completion-cost objectives on parallel machines, any schedule without these moves can be forced into unbounded approximation ratios (Scheduling to Approximate Minimization Objectives on Identical Machines). Phasing sub-problems happen to be cheap to checkpoint, since the state is just a partial partition of reads or a solver population. We therefore propose a scheduler that ranks windows by predicted weight-per-unit-work, and that preempts and migrates windows whose observed cost exceeds their prediction. We test whether this beats the simple dispatching rules a practitioner would reach for first.

Core Claim

In streaming read-based phasing, a density-priority scheduler with checkpointed preemption and migration of straggler windows will substantially reduce weighted mean time-to-phased-window compared with first-in-first-out dynamic queues and static block assignment. It will also keep total runtime and switch error within a small margin of batch phasing.

We add a second, falsifiable claim. Preemption matters beyond ordering: removing it should recover most of the latency loss that the stragglers cause. If a plain weighted-shortest-predicted-job-first queue matches the full scheduler, the scheduling theory adds nothing beyond Smith's rule and good runtime prediction. We will report that outcome if it happens.

What Exists and What Does Not

The closest phasing work to parallel scheduling is GenHap (GenHap: Evolutionary Computation For Haplotype Assembly; preprint; GenHap: A novel computational method based on genetic algorithms for haplotype assembly). GenHap solves weighted Minimum Error Correction, the NP-hard problem of flipping the fewest quality-weighted read bases so that reads split cleanly into two haplotypes. It uses a genetic algorithm and cuts the read matrix into fixed blocks that a master process hands to workers. GenHap is offline and batch, and it measures only total wall-clock time. It never asks when individual blocks finish, and its static allocation lets the slowest block hold up the whole batch.

On the accuracy side, other pipelines optimize contiguity and switch error with no notion of per-block latency. PECAT does haplotype-aware correction and string-graph unzipping (De novo diploid genome assembly using long noisy reads). NanoFilter adds a consistency filter for insertions and deletions feeding Margin and HapDup (NanoFilter). PECAT also supplies the constraint that produces our stragglers: its pipelines degrade where heterozygosity falls below 0.0005.

The scheduling side supplies the method. Smith's ratio rule, which orders jobs by weight over processing time, is optimal on one machine. The density-based online extensions of Megow and Schulz keep good ratios on parallel machines. The select-and-permute framework (Khuller et al.) turns an offline "which jobs to finish in this doubling time interval" subroutine into an online algorithm with constant competitive ratios. Two results are negative and explain why naive greedy dispatching is fragile. Greedy preemptive flow-time scheduling becomes NP-hard with two machines (A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling). Online weighted flow time degrades from logarithmic to polynomial lower bounds on multiple machines because routing decisions cannot be undone (Improved Online Algorithm for Weighted Flow Time).

Two further results are directly relevant. Constant-competitive multi-machine SRPT needs slightly faster machines (Online Scheduling on Identical Machines using SRPT), so we will run spare-capacity experiments. Our processing times are predictions with error, which is exactly the setting of distortion-oblivious scheduling (Distortion-Oblivious Algorithms for Scheduling on Multiple Machines). The research file found no prior work that frames phasing as a latency-weighted scheduling problem.

We deliberately do not pursue the tempting mapping of "haplotypes as machines, reads as jobs, allele conflicts as incompatibility cliques" onto Jansen et al.. Their polynomial result for identical machines rests on a completion-time layering that has no meaning inside minimum error correction. The analogy is formal rather than useful.

Research Program

Each job is a window of consecutive heterozygous sites that overlaps its neighbours so that phase can be stitched across boundaries. A window $j$ is released at time $r_j$, when its read depth passes a sufficiency threshold. It has weight $w_j$ and completion time $C_j$, the moment its phase is reported. The objective is

$$\min \sum_j w_j (C_j - r_j),$$

which is weighted flow time: how long, on average, a weighted window waits between becoming solvable and being reported. We also track the conventional makespan, the finish time of the last window, so that we can see what the latency gain costs.

Weights come from two sources. The first is a clinical target list, such as genes of interest in the style of the targeted PKD1 setting (Targeted long-read sequencing enables higher diagnostic yield of ADPKD). The second is informativeness, measured as the count of variants that pass NanoFilter's co-occurrence consistency score.

The first component is a runtime predictor. It estimates each window's solver cost $\hat p_j$ from depth, number of heterozygous sites, local heterozygosity, and read-consistency statistics. The model is trained on logged solves. The second component is the scheduler. It runs select-and-permute over doubling intervals, and within each interval it orders windows by $w_j/\hat p_j$.

The third component carries the key ingredient. Workers checkpoint their state: a genetic-algorithm population for GenHap-style solving, or a partial read partition for exact dynamic programming on low-depth windows. When a window's elapsed cost exceeds a multiple of $\hat p_j$, it is preempted, re-queued with an updated estimate, and resumed on whichever worker frees up next. Preempted windows can also be split horizontally, GenHap-style, so that several workers share one straggler.

On the theory side we aim for a modest result. We want a competitive bound for this policy under speed augmentation that degrades gracefully with prediction error, following the SRPT augmentation and distortion-oblivious analyses. We will not claim new worst-case results beyond that.

Baselines

The naive reference point is batch phasing. We wait for all reads, then run the pipeline once; every window finishes at the end, so weighted flow time equals the weighted sum of end-time minus release time. The phasing solver itself is held fixed across all conditions.

The strongest existing phasing system on the scheduling question is GenHap's static master-worker allocation, because it is the only published parallel wMEC design. We run it on the same cores with its block size tuned on held-out chromosomes. Its reported numbers are "roughly 10 minutes" on NA12878 PacBio chromosome 22, with "87% agreement with benchmark solutions", and Haplotype Error rates "under 2.5%" on noisy PacBio GemSIM simulations. The research file reports no latency or weighted-flow-time result for GenHap or for any phasing tool, so beating it on latency has no published target. Instead we define success as at least a twofold reduction in weighted flow time relative to both GenHap-static and the first-in-first-out queue, with makespan within 10% and switch error within 0.1 absolute percentage points of batch.

The strongest generic competitor is a dynamic first-in-first-out work queue with work stealing, the default in OpenMP- or MPI-based pipelines. We also run longest-predicted-first list scheduling as the makespan-oriented rule, and weighted shortest-predicted-job-first without epochs or preemption. The last of these is Smith's rule with our own predictor, and it is the ablation that matters most. All policies get identical cores, identical read streams, the same predictor, and equal tuning budgets for their thresholds.

Two more ablations isolate individual components. Removing preemption and migration from the full scheduler isolates the key ingredient. Replacing $\hat p_j$ with the true runtime, an oracle, measures how much of the result depends on prediction quality.

Why not just…?

Why not just use work stealing? Work stealing balances idle time well, and it may nearly match us on makespan. It is blind to weights, and it cannot rescue a worker stuck on a straggler: stealing moves queued jobs, not the running one. The theory predicts the gap will grow with straggler frequency (Improved Online Algorithm for Weighted Flow Time). We test this directly by varying the fraction of low-heterozygosity windows on synthetic data. If work stealing stays within 20% of our method across that sweep, the proposal's premise fails.

Why not just phase the clinical genes first? This is a real threat. With a few binary-priority targets, a static priority list may be all anyone needs. Our method only earns its place when weights are graded and costs vary widely within the high-priority set, or when a target gene is itself a straggler, as repeat-rich genes like PKD1 may be. We run a target-list-first baseline and report separately the regime where it ties us.

Why not just use Smith's rule with a good runtime predictor? If ordering is all that matters, weighted shortest-predicted-first will match the full scheduler, and the preemption ablation will show it. That outcome would still be useful: it would tell pipeline builders that a runtime model plus a priority queue is enough. The oracle-runtime ablation separates "ordering is enough" from "predictions are too poor for ordering to work."

Why not just downsample to make every window cheap? Downsampling removes stragglers, but it discards linkage. GenHap reports that retaining up to 565× depth is feasible and beneficial, whereas HapCol halts above 30×. NanoFilter shows that crude filtering loses informative variants and raises switch error. We include a downsampled-to-30× condition, which is expected to be fast but less accurate.

Proposed Experiments

We use HG002 Nanopore R10 reads, scored against the GIAB v4.2.1 phased truth set, which NanoFilter uses. Reads are replayed in sequencing-timestamp order where available and in random order otherwise. We also use NA12878 PacBio chromosome 22, including GenHap's high-depth data, for depth stress. GemSIM-style simulations at 30× and 60× with a controlled heterozygosity dip below 0.0005 let us vary straggler frequency.

The metrics are weighted flow time, time-to-first-report for target genes, makespan, CPU-hours, switch and Hamming error, and phase-block N50. The accuracy metrics serve as guards to show that streaming and stitching do not cost accuracy relative to batch.

Three checks decide the question. First, the full scheduler must beat first-in-first-out and GenHap-static on weighted flow time at matched accuracy. Second, the no-preemption ablation must lose most of that gain as straggler frequency rises. Third, the oracle and learned predictors must be close. A failure of the third check limits the result to what runtime prediction can support. A failure of the second check means the contribution reduces to Smith's rule plus a predictor, which is still worth reporting.