Alignment

class Alignment(values)

exported from alignment

An alignment between two related sequences.

Consider this alignment between two strings:

|it's| |aligned!|
|    \ \        |
|it is| |aligned|

An alignment stores all the indices that are known to correspond between the original and modified sequences. For the above example, it would be

let a = new Alignment([
    [0, 0],
    [4, 5],
    [5, 6],
    [13, 13],
]);

Alignments can be used to answer questions like, “what’s the smallest range of the original sequence that is guaranteed to contain this part of the modified sequence?” For example, the range (0, 5) (“it is”) is known to match the range (0, 4) (“it’s”) of the original sequence.

console.log(a.original_bounds(0, 5));
// [0, 4]

Results may be imprecise if the alignment is too course to match the exact inputs:

console.log(a.original_bounds(0, 2));
// [0, 4]

A more granular alignment like this:

|i|t|'s| |a|l|i|g|n|e|d|!|
| | |  \ \ \ \ \ \ \ \ \ /
|i|t| is| |a|l|i|g|n|e|d|
a = new Alignment([
    [0, 0], [1, 1], [2, 2], [4, 5], [5, 6], [6, 7], [7, 8],
    [8, 9], [9, 10], [10, 11], [11, 12], [12, 13], [13, 13],
]);

Can be more precise:

console.log(a.original_bounds(0, 2));
// [0, 2]

Create a new Alignment.

Arguments
  • values (Iterable) – The pairs of indices to align. Each element should be a pair destructurable as [x, y], where x is the original sequence position and y is the modified sequence position.

Alignment.compose(other)
Arguments
  • other (alignment.Alignment) –

Returns

alignment.Alignment – An alignment equivalent to applying this first, then other.

Alignment.concat(others)

Concatenate this alignment together with one or more others.

Arguments
  • others (alignment.Alignment[]) –

Returns

alignment.Alignment

Alignment.equals(other)
Arguments
  • other (alignment.Alignment) –

Returns

boolean – Whether this alignment is the same as other.

Alignment.identity(size)

Create an identity alignment of the given size, which maps all intervals to themselves.

Arguments
  • size (number) – The size of the sequences to align.

Returns

alignment.Alignment – The identity alignment for the bounds [0, size].

Alignment.identity(start, end)

Create an identity alignment between the given bounds.

Arguments
  • start (number) – The first index to align.

  • end (number) – The last index to align.

Returns

alignment.Alignment – The identity alignment for the bounds [start, end].

Alignment.identity(bounds)

Create an identity alignment with the given bounds.

Arguments
  • bounds (alignment.Bounds) – The bounds of the alignment (e.g. [1, 5]).

Returns

alignment.Alignment – The identity alignment for the given bounds.

Alignment.infer(original, modified, costFn)

Infer the alignment between two sequences with the lowest edit distance.

Warning: this operation has time complexity O(N*M), where N and M are the lengths of the original and modified sequences, and so should only be used for relatively short sequences.

Arguments
  • original (Iterable) – The original sequence.

  • modified (Iterable) – The modified sequence.

  • costFn (alignment.CostFn) – A function returning the cost of performing an edit. costFn(a, b) returns the cost of replacing a with b. costFn(a, undefined) returns the cost of deleting a, and costFn(undefined, b) returns the cost of inserting b. By default, all operations have cost 1 except replacing identical elements, which has cost 0.

Returns

alignment.Alignment – The inferred alignment.

Alignment.inverse()
Returns

alignment.Alignment – The inverse of this alignment, from the modified to the original sequence.

Alignment.length

type: number

The number of entries in this alignment.

Alignment.modifiedBounds()
Returns

alignment.Bounds – The bounds of the modified sequence.

Alignment.modifiedBounds(start, end)

Maps a subrange of the original sequence to the modified sequence.

Arguments
  • start (number) – The start of the span in the original sequence.

  • end (number) – The end of the span in the original sequence.

Returns

alignment.Bounds – The bounds of the corresponding span in the modified sequence.

Alignment.modifiedBounds(bounds)

Maps a subrange of the original sequence to the modified sequence.

Arguments
  • bounds (alignment.Bounds) – The bounds of the span in the original sequence.

Returns

alignment.Bounds – The bounds of the corresponding span in the modified sequence.

Alignment.originalBounds()
Returns

alignment.Bounds – The bounds of the original sequence.

Alignment.originalBounds(start, end)

Maps a subrange of the modified sequence to the original sequence.

Arguments
  • start (number) – The start of the span in the modified sequence.

  • end (number) – The end of the span in the modified sequence.

Returns

alignment.Bounds – The bounds of the corresponding span in the original sequence.

Alignment.originalBounds(bounds)

Maps a subrange of the modified sequence to the original sequence.

Arguments
  • bounds (alignment.Bounds) – The bounds of the span in the modified sequence.

Returns

alignment.Bounds – The bounds of the corresponding span in the original sequence.

Alignment.shift(deltaO, deltaM)

Shift this alignment.

Arguments
  • deltaO (number) – The distance to shift the original sequence.

  • deltaM (number) – The distance to shift the modified sequence.

Returns

alignment.Alignment – An alignment with all the positions shifted by the given amounts.

Alignment.slice(start, end)

Extract a slice of this alignment.

Arguments
  • start (undefined|number) – The position to start from.

  • end (undefined|number) – The position to end at.

Returns

alignment.Alignment – The requested slice as a new Alignment.

Alignment.sliceByModified(start, end)

Slice this alignment by a span of the modified sequence.

Arguments
  • start (number) – The start of the span in the modified sequence.

  • end (number) – The end of the span in the modified sequence.

Returns

alignment.Alignment – The requested slice of this alignment.

Alignment.sliceByModified(bounds)

Slice this alignment by a span of the modified sequence.

Arguments
  • bounds (alignment.Bounds) – The bounds of the span in the modified sequence.

Returns

alignment.Alignment – The requested slice of this alignment.

Alignment.sliceByOriginal(start, end)

Slice this alignment by a span of the original sequence.

Arguments
  • start (number) – The start of the span in the original sequence.

  • end (number) – The end of the span in the original sequence.

Returns

alignment.Alignment – The requested slice of this alignment.

Alignment.sliceByOriginal(bounds)

Slice this alignment by a span of the original sequence.

Arguments
  • bounds (alignment.Bounds) – The bounds of the span in the original sequence.

Returns

alignment.Alignment – The requested slice of this alignment.

Alignment.values

type: keyof:BiIndex[]

The pairs of aligned indices in this alignment.