de.jstacs.algorithms.alignment

Class Alignment

java.lang.Object

de.jstacs.algorithms.alignment.Alignment

public class Alignment
extends Object

Class for computing optimal alignments using Needleman-Wunsch algorithm of for affine gap costs Gotohs algorithm. The class also provides the possibility of specifying the number of off-diagonals. In this case, the current implementation helps to reduce the runtime but not the memory consumption.

Author:

Jan Grau, Jens Keilwagen

See Also:

AffineCosts

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Alignment.AlignmentType

Field Summary

Fields

Modifier and Type	Field and Description
protected AffineCosts	aCosts The affine alignment costs
protected Costs	costs The alignment costs
protected double[][][]	d The matrices holding the edit distances
protected int	l1 The length of the sub-sequence of the first sequence that is aligned
protected int	l2 The length of the sub-sequence of the second sequence that is aligned
protected Sequence	s1 The first sequence
protected Sequence	s2 The second sequence
protected int	startS1 The start position in the first sequence
protected int	startS2 The start position in the second sequence
protected Alignment.AlignmentType	type The type of the alignment

Constructor Summary

Constructors

Constructor and Description
Alignment(Costs costs) Creates a new Alignment instance that aligns the sequences s1 and s2 using the costs defined in costs.
Alignment(Costs costs, int offDiagonal) Creates a new Alignment instance that aligns the sequences s1 and s2 using the costs defined in costs and a banded version of the alignment algorithm.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	computeAlignment(Alignment.AlignmentType type, Sequence s1, int startS1, int endS1, Sequence s2, int startS2, int endS2) Computes the alignment between s1 and s2 starting from startS1 and startS2 until endS1 and endS2, respectively.
boolean	computeAlignment(Alignment.AlignmentType type, Sequence s1, Sequence s2) Computes the alignment between s1 and s2.
PairwiseStringAlignment	getAlignment(Alignment.AlignmentType type, Sequence s1, int startS1, int endS1, Sequence s2, int startS2, int endS2) Computes and returns the alignment of s1 and s2 (Alignment(Costs)).
PairwiseStringAlignment	getAlignment(Alignment.AlignmentType type, Sequence s1, Sequence s2) Computes and returns the alignment of s1 and s2 (Alignment(Costs)).
protected PairwiseStringAlignment	getAlignment(int[] index) Returns the optimal alignment (backtrace) according to matrix index[0] until positions index[1] and index[2] in the first and second sequence, respectively.
double	getCost(int end1, int end2) Returns the costs until positions end1 and end2 of the last alignment computed using computeAlignment(AlignmentType, Sequence, Sequence).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

startS1

protected int startS1

The start position in the first sequence

startS2

protected int startS2

The start position in the second sequence

s1

protected Sequence s1

The first sequence

s2

protected Sequence s2

The second sequence

l1

protected int l1

The length of the sub-sequence of the first sequence that is aligned

l2

protected int l2

The length of the sub-sequence of the second sequence that is aligned

costs

protected Costs costs

The alignment costs

aCosts

protected AffineCosts aCosts

The affine alignment costs

type

protected Alignment.AlignmentType type

The type of the alignment

d

protected double[][][] d

The matrices holding the edit distances

Constructor Detail

Alignment

public Alignment(Costs costs)

Creates a new Alignment instance that aligns the sequences s1 and s2 using the costs defined in costs.

Parameters:

costs - the costs

Alignment

public Alignment(Costs costs,
         int offDiagonal)

Creates a new Alignment instance that aligns the sequences s1 and s2 using the costs defined in costs and a banded version of the alignment algorithm. If the alignment is performed for Sequences of different length, the number of secondary diagonals must be at least as large as the difference of the lengths.

Parameters:

costs - the costs

offDiagonal - the number of secondary diagonals at both sides of the diagonal

Method Detail

getAlignment

public PairwiseStringAlignment getAlignment(Alignment.AlignmentType type,
                                   Sequence s1,
                                   Sequence s2)

Computes and returns the alignment of s1 and s2 (Alignment(Costs)).

Parameters:

type - the type of the alignment

s1 - the first sequence

s2 - the second sequence

Returns:

the alignment

getAlignment

public PairwiseStringAlignment getAlignment(Alignment.AlignmentType type,
                                   Sequence s1,
                                   int startS1,
                                   int endS1,
                                   Sequence s2,
                                   int startS2,
                                   int endS2)

Computes and returns the alignment of s1 and s2 (Alignment(Costs)).

Parameters:

type - the type of the alignment

s1 - the first sequence

startS1 - the start position in the first sequence

endS1 - the end position in the first sequence

s2 - the second sequence

startS2 - the start position in the second sequence

endS2 - the end position in the second sequence

Returns:

the alignment

computeAlignment

public boolean computeAlignment(Alignment.AlignmentType type,
                       Sequence s1,
                       Sequence s2)

Computes the alignment between s1 and s2. Afterwards, alignment costs may be obtained by getCost(int, int). To also obtain the alignment, use getAlignment(AlignmentType, Sequence, Sequence).

Parameters:

type - the type of the alignment

s1 - the first sequence

s2 - the second sequence

Returns:

if the alignment could be computed

computeAlignment

public boolean computeAlignment(Alignment.AlignmentType type,
                       Sequence s1,
                       int startS1,
                       int endS1,
                       Sequence s2,
                       int startS2,
                       int endS2)

Computes the alignment between s1 and s2 starting from startS1 and startS2 until endS1 and endS2, respectively. Afterwards, alignment costs may be obtained by getCost(int, int). To also obtain the alignment, use getAlignment(AlignmentType, Sequence, Sequence).

Parameters:

type - the type of the alignment

s1 - the first sequence

startS1 - the start position in the first sequence

endS1 - the end position (exclusive) in the first sequence

s2 - the second sequence

startS2 - the start position in the second sequence

endS2 - the end position (exclusive) in the second seuqence

Returns:

if the alignment could be computed

getCost

public double getCost(int end1,
             int end2)

Returns the costs until positions end1 and end2 of the last alignment computed using computeAlignment(AlignmentType, Sequence, Sequence).

Parameters:

end1 - the end position in the first sequence

end2 - the end position in the second sequence

Returns:

the costs

getAlignment

protected PairwiseStringAlignment getAlignment(int[] index)

Returns the optimal alignment (backtrace) according to matrix index[0] until positions index[1] and index[2] in the first and second sequence, respectively. The method computeAlignment(AlignmentType, Sequence, Sequence) must be called before obtaining the alignment, since this method only does the backtracing in the matrices.

Parameters:

index - the indexes of the matrix element

Returns:

the alignment