Jim Shaw; Yun William Yu

Proving sequence aligners can guarantee accuracy in almost O(m log n) time through an average-case analysis of the seed-chain-extend heuristic

(Downloading may take up to 30 seconds. If the slide opens in your browser, select File -> Save As to save it.)

Click on image to view larger version.

Figure 4.

The aligned fraction of the aligned reads, which is chain length divided by read length. We fit a function of the form $\text{[math]}$ , where m is the read length (x-axis), and display the resulting R² values. Aligned fraction is an upper bound for recoverability, and our lower bound on recoverability (and also aligned fraction) is $\text{[math]}$ , which the data suggest may be too conservative.