Figure 1

Local alignment. Gapped local alignment scores and the corresponding directed paths for two subsequences $\mathbf{A}(0,10]=\mathrm{TATATGCCTT}$ and $\mathbf{B}(0,10]=\mathrm{CCATTGCACA}$ of sequences drawn from the nucleotide alphabet $\left\{\mathrm{A},\mathrm{C},\mathrm{G},\mathrm{T}\right\}$. The nucleotide scoring matrix in the figure is commonly used in applications: $S\left(a,b\right)=4$ if $a=b$ and $-5$ otherwise and the affine gap penalty $\Delta \left(g\right)=2+g$. The vertex $\left(i,j\right)=\left(10,10\right)$ is in the northeast corner of the figure with the origin $(0,0)$ at the southwest corner. The cell $(i,j)$ corresponding to the letter pair $\left(A_i,B_j\right)$ displays the corresponding local score ${\widehat{S}}_{i,j}$. A local score of 0 indicates that no path of positive weight ends at the corresponding point. The optimal local path, which ends at point (8,9), e.g., consists of eight edges, in order: 2 northeast, 1 east, 3 northeast, 1 north, and 1 northeast. It corresponds to the optimal local sequence alignment of $\mathbf{A}(0,10]$ and $\mathbf{B}(0,10]$, The local score ${\widehat{S}}_{8,9}=4+4-3+4+4+4-3+4=18$ is the sum of the corresponding edges and represents the path of greatest weight ending at point $\left(8,9\right)$. The score is also the greatest weight of any path within the rectangle displayed, so it also corresponds to the local maximum score ${\widehat{M}}_{10,10}=18$.Reuse & Permissions

Figure 2

Single-sided asymptotic regression. The figure indicates a typical plot relevant to single-sided asymptotic regression, with the transient regime on the left, the asymptotic regime on the right, and an ill-defined change point separating the two regimes. Once in the asymptotic regime, the data point approximates a horizontal line $y=\beta$. The rest of this caption is pertinent only to the Results section, as follows. This figure displays estimates $y_i$ for $\beta ={\lambda }_{n-5,n}$ from Eq. (2) against sequence length $t=n$ as small open circles (○) with error bars. (Some error bars are small and are not readily visible). The error bars indicate standard errors from 1 000 000 random sequence pairs. The solid horizontal line shows the present best estimate $\beta =\lambda \approx 0.2666\pm 0.0003$ [32]. For single-sided asymptotic regression, data in the asymptotic regime are indicated by large open circles (○); the estimated $\widehat{\beta }$ is indicated by a thick dotted horizontal line (indistinguishable from the solid horizontal line). For robust regression with Andrews’ wave function, data in the asymptotic regime are indicated by closed circles (•); the estimated $\widehat{\beta }$ is indicated by a dashed horizontal line (barely distinguishable from the solid horizontal line). The values $c=2$ and $a=0.5$ were chosen for single-sided asymptotic regression and robust regression with Andrews’ wave function, respectively, because they minimized the absolute difference between the estimated $\beta$ and the present best estimate $\beta =\lambda \approx 0.2666\pm 0.0003$. (Table  summarizes the different estimates of $\beta$ from different cutoff values $c$ and parameters $a$.)Reuse & Permissions

Figure 3

Double-sided asymptotic regression. The figure indicates a typical plot relevant to double-sided asymptotic regression, with the transient regime on the left, the asymptotic regime on the right (which is eventually overtaken by a noncompliant regime where the statistical model fails), and two ill-defined change points separating the three regimes. The rest of this caption is pertinent only to the Results section, as follows. This figure displays estimates $y_i$ for $\beta =K$ from Eq. (3) against global score $t=s$ as small open circles (○) with error bars. The error bars indicate standard errors from 1 000 000 random sequence pairs. The solid horizontal line shows the present best estimate $\beta =K\approx 0.0409\pm 0.0003$ [32]. For double-sided asymptotic regression, data in the asymptotic regime are indicated by large open circles (○); the estimated $\widehat{\beta }$ is indicated by a thick dotted horizontal line (barely distinguishable from the solid horizontal line). For robust regression with Andrews’ wave function, data are indicated by closed circles (•); the estimated $\widehat{\beta }$ is represented by a dashed horizontal line. (Note that, in fact, robust regression outliers break up the single asymptotic interval indicated by the dashed line.) For each method, $c=0.5$ and $a=0.5$ minimized the absolute difference between the estimated $K$ and the present best estimate $\beta =K\approx 0.0409\pm 0.0003$. (Table  summarizes the different estimates of $K$ from different cutoff values $c$ and parameters $a$.)Reuse & Permissions