Package Bio :: Module pairwise2
[hide private]
[frames] | no frames]

Module pairwise2

source code

Pairwise sequence alignment using a dynamic programming algorithm.

This provides functions to get global and local alignments between two sequences. A global alignment finds the best concordance between all characters in two sequences. A local alignment finds just the subsequences that align the best.

When doing alignments, you can specify the match score and gap penalties. The match score indicates the compatibility between an alignment of two characters in the sequences. Highly compatible characters should be given positive scores, and incompatible ones should be given negative scores or 0. The gap penalties should be negative.

The names of the alignment functions in this module follow the convention <alignment type>XX where <alignment type> is either "global" or "local" and XX is a 2 character code indicating the parameters it takes. The first character indicates the parameters for matches (and mismatches), and the second indicates the parameters for gap penalties.

The match parameters are:

CODE  DESCRIPTION
x     No parameters. Identical characters have score of 1, otherwise 0.
m     A match score is the score of identical chars, otherwise mismatch
      score.
d     A dictionary returns the score of any pair of characters.
c     A callback function returns scores.

The gap penalty parameters are:

CODE  DESCRIPTION
x     No gap penalties.
s     Same open and extend gap penalties for both sequences.
d     The sequences have different open and extend gap penalties.
c     A callback function returns the gap penalties.

All the different alignment functions are contained in an object align. For example:

>>> from Bio import pairwise2
>>> alignments = pairwise2.align.globalxx("ACCGT", "ACG")

will return a list of the alignments between the two strings. For a nice printout, use the format_alignment method of the module:

>>> from Bio.pairwise2 import format_alignment
>>> print(format_alignment(*alignments[0]))
ACCGT
|||||
A-CG-
  Score=3
<BLANKLINE>

All alignment functions have the following arguments:

The other parameters of the alignment function depend on the function called. Some examples:

To see a description of the parameters for a function, please look at the docstring for the function via the help function, e.g. type help(pairwise2.align.localds) at the Python prompt.

Classes [hide private]
  identity_match
Create a match function for use in an alignment.
  dictionary_match
Create a match function for use in an alignment.
  affine_penalty
Create a gap function for use in an alignment.
Functions [hide private]
 
_align(sequenceA, sequenceB, match_fn, gap_A_fn, gap_B_fn, penalize_extend_when_opening, penalize_end_gaps, align_globally, gap_char, force_generic, score_only, one_alignment_only)
Return a list of alignments between two sequences or its score (PRIVATE).
source code
 
_make_score_matrix_generic(sequenceA, sequenceB, match_fn, gap_A_fn, gap_B_fn, penalize_end_gaps, align_globally, score_only)
Generate a score and traceback matrix according to Needleman-Wunsch (PRIVATE).
source code
 
_recover_alignments(sequenceA, sequenceB, starts, score_matrix, trace_matrix, align_globally, gap_char, one_alignment_only, gap_A_fn, gap_B_fn)
Do the backtracing and return a list of alignments (PRIVATE).
source code
 
_find_start(score_matrix, align_globally)
Return a list of starting points (score, (row, col)) (PRIVATE).
source code
 
_clean_alignments(alignments)
Take a list of alignments and return a cleaned version (PRIVATE).
source code
 
_finish_backtrace(sequenceA, sequenceB, ali_seqA, ali_seqB, row, col, gap_char)
Add remaining sequences and fill with gaps if neccessary (PRIVATE).
source code
 
_find_gap_open(sequenceA, sequenceB, ali_seqA, ali_seqB, end, row, col, col_gap, gap_char, score_matrix, trace_matrix, in_process, gap_fn, target, index, direction)
Find the starting point(s) of the extended gap (PRIVATE).
source code
 
calc_affine_penalty(length, open, extend, penalize_extend_when_opening)
Calculate a penality score for the gap function.
source code
 
print_matrix(matrix)
Print out a matrix for debugging purposes.
source code
 
format_alignment(align1, align2, score, begin, end)
Format the alignment prettily into a string.
source code
Variables [hide private]
  MAX_ALIGNMENTS = 1000
  align = align()
  _PRECISION = 1000
  __package__ = 'Bio'
Function Details [hide private]

_make_score_matrix_generic(sequenceA, sequenceB, match_fn, gap_A_fn, gap_B_fn, penalize_end_gaps, align_globally, score_only)

source code 

Generate a score and traceback matrix according to Needleman-Wunsch (PRIVATE).

This implementation allows the usage of general gap functions and is rather slow. It is automatically called if you define your own gap functions. You can force the usage of this method with force_generic=True.

_recover_alignments(sequenceA, sequenceB, starts, score_matrix, trace_matrix, align_globally, gap_char, one_alignment_only, gap_A_fn, gap_B_fn)

source code 

Do the backtracing and return a list of alignments (PRIVATE).

Recover the alignments by following the traceback matrix. This is a recursive procedure, but it's implemented here iteratively with a stack.

sequenceA and sequenceB may be sequences, including strings, lists, or list-like objects. In order to preserve the type of the object, we need to use slices on the sequences instead of indexes. For example, sequenceA[row] may return a type that's not compatible with sequenceA, e.g. if sequenceA is a list and sequenceA[row] is a string. Thus, avoid using indexes and use slices, e.g. sequenceA[row:row+1]. Assume that client-defined sequence classes preserve these semantics.

_find_start(score_matrix, align_globally)

source code 

Return a list of starting points (score, (row, col)) (PRIVATE).

Indicating every possible place to start the tracebacks.

_clean_alignments(alignments)

source code 

Take a list of alignments and return a cleaned version (PRIVATE).

Remove duplicates, make sure begin and end are set correctly, remove empty alignments.