nuget
api documents
Global alignment (Needleman-Wunsch) with a k-band heuristic.
Only cells with |i - j| <= k are evaluated, which turns the O(l1l2) dynamic programming into O(l1min(l2, 2k)) time.
The implementation keeps two rolling row buffers instead of the full score matrix, so that the working set is O(k) rather than O(l1*l2).
01 Syntax
02 Methods
| Name | Overloads | Summary |
|---|---|---|
| .ctor | 1 | open the k-band alignment search engine |
| CalculateEditDistance | 1 | Global alignment and function to calculate the edit distances + 0 diagonal + 1 left + 2 up |
| AlignBanded | 1 | Fill the k-band and backtrace the optimal global alignment. |
| Backtrace | 1 | Walk the traceback buffer back from (l1, l2) to (0, 0) and build the two aligned strings. |
03 Fields
| Name | Overloads | Summary |
|---|---|---|
| K | 1 | The k-band width requested by the caller. |
| globalAlign | 1 | The output buffer of the last alignment, slot 0 is the aligned first sequence and slot 1 is the aligned second sequence. |
| UNREACHABLE | 1 | A cell that is out of the k-band, or that has not been computed yet. |
04 Members
String(), Int32)open the k-band alignment search engine
| Name | Type | Description |
|---|---|---|
globalAlign | String() | A buffer of at least two slots for receiving the alignment result of the last KBandSearch.CalculateEditDistance() call. |
k | Int32 | The k-band width, a small value runs faster but may miss the optimal path when the two sequences are highly divergent. |
String, String)Global alignment and function to calculate the edit distances
A k-band that is narrower than the length difference |l1 - l2| can never reach the target cell. Instead of throwing, the band is enlarged automatically here (in the worst case up to the full matrix, i.e. an exact Needleman-Wunsch alignment).
| Name | Type | Description |
|---|---|---|
seq1$ | String | - |
seq2$ | String | - |
The edit distance between seq1 and seq2, the two aligned strings are written into the KBandSearch.globalAlign buffer.
String, String, Int32, Int32, Int32)Fill the k-band and backtrace the optimal global alignment.
Row buffers are addressed by the column window of the current row: row i covers the columns [jStart, jEnd] and stores cell (i, j) at the slot (j - jStart) + 1. Slot 0 and slot (w + 1) are permanent sentinels that always hold KBandSearch.UNREACHABLE, so that the inner loop needs no boundary check at all.
As the window of row i-1 is shifted by at most one column against the window of row i, the neighbouring cells are located at:
diag (i-1, j-1) => prev[cj + delta] up (i-1, j) => prev[cj + delta + 1] left (i, j-1) => cur[cj]
in which delta = jStart(i) - jStart(i-1) is either 0 or 1.
The edit distance, or a negative value when the target cell (l1, l2) turns out to be unreachable inside the band of width k.
Byte(), Int32, Int32, Int32, Int32, String, String, Int32)Walk the traceback buffer back from (l1, l2) to (0, 0) and build the two aligned strings.
The k-band width requested by the caller.
The effective width used internally may be enlarged automatically when the requested one is too small to make the target cell reachable, see KBandSearch.CalculateEditDistance().
The output buffer of the last alignment, slot 0 is the aligned first sequence and slot 1 is the aligned second sequence.
This buffer is shared by all of the alignments made by this instance, i.e. the class is NOT thread safe, each worker thread requires its own instance.
A cell that is out of the k-band, or that has not been computed yet.
NOTE: this sentinel must never take part in any arithmetic expression, adding one to it overflows into Int32 and would make an unreachable direction look like the cheapest one.