Package neobio.alignment

Provides implementation of sequence alignment algorithms.

See:
Description

Interface Summary

Matrix

This interface defines a minimal set of operations that a matrix must implement.

Class Summary

AlignmentBlock	This class is used by the CrochemoreLandauZivUkelson algorithm to store the information of an alignment block.
BasicScoringScheme	This class implements a basic scoring scheme.
CharSequence	This class implements a sequence of characters stored as an array that provides random access to any position in constant time.
CrochemoreLandauZivUkelson	This abstract class is the superclass of both global and local sequence alignment algorithms (with linear gap penalty function) due to Maxime Crochemore, Gad Landau and Michal Ziv-Ukelson (2002).
CrochemoreLandauZivUkelsonGlobalAlignment	This class implements the global pairwise sequence alignment algorithm (with linear gap penalty function) due to Maxime Crochemore, Gad Landau and Michal Ziv-Ukelson (2002).
CrochemoreLandauZivUkelsonLocalAlignment	This class implements the local pairwise sequence alignment algorithm (with linear gap penalty function) due to Maxime Crochemore, Gad Landau and Michal Ziv-Ukelson (2002).
Factor	This class is used by FactorSequence to create a linked list of factors of a text as induced by its Lempel-Ziv (LZ78) factorisation.
FactorSequence	This class builds a list of factors of a character sequence as induced by its Lempel-Ziv (LZ78) factorisation.
LocalAlignmentBlock	This class is used by the CrochemoreLandauZivUkelsonLocalAlignment algorithm to store the information of an alignment block.
NeedlemanWunsch	This class implements the classic global alignment algorithm (with linear gap penalty function) due to S.B.Needleman and C.D.Wunsch (1970).
OutMatrix	Implements an interface to the OUT matrix of a block.
PairwiseAlignment	This class is the product of a pairwise alignment, generated by one subclasses of PairwiseAlignmentAlgorithm.
PairwiseAlignmentAlgorithm	This abstract class is the superclass of all classes implementing pairwise sequence alignment algorithms.
ScoringMatrix	This class implements a scoring scheme based on a substitution matrix.
ScoringScheme	This abstract class is the superclass of all scoring schemes.
Smawk	This class implement the SMAWK algorithm to compute column maxima on a totally monotone matrix as described.
SmithWaterman	This class implement the classic local alignment algorithm (with linear gap penalty function) due to T.F.Smith and M.S.Waterman (1981).
Trie	This class implements a trie, or a digital search tree.

Exception Summary

IncompatibleScoringSchemeException	Signals that an scoring scheme is not compatible with the sequences being aligned.
InvalidScoringMatrixException	Signals that the substitution matrix does not comply with the specification (see ScoringMatrix for details).
InvalidSequenceException	Signals that the sequence does not comply with the specification (see CharSequence or FactorSequence for details).

Package neobio.alignment Description

Provides implementation of sequence alignment algorithms.

Pairwise sequence alignment algorithms:

• Needleman & Wunsch (global alignment)
• Smith & Waterman (local alignment)
• Crochemore, Landau & Ziv-Ukelson for global alignment
• Crochemore, Landau & Ziv-Ukelson for local alignment

All algorithms use linear gap penalty functions (additive gap costs).

Main supporting classes:

• CharSequence and FactorSequence: store information about a sequence that can be aligned with another sequence using one alignment algorithm; they wrap the main input of alignment algorithms to provide ways of reading the data.
• ScoringScheme and its subclasses: implement scoring schemes used by alignment algorithms to calculate the similary between two sequences.
• PairwiseAlignment: this is the result of an execution of a pairwise alignment algorithm. It basically contains a string representation of both sequences with gaps (represented with dashes) that produces a highest scoring alignment between them.
• Smawk: both of Crochemore, Landau & Ziv-Ukelson's algorithms rely on this class to provide an implementation of an algorithm, nicknamed SMAWK in the literature, that computes in linear time all column (or row) maxima of a totally monotone matrix.