/*
* FastNW: Fast Needleman-Wunsch
* Copyright (C) 2014 Jonathan Richards
*
* Written by Jonathan Richards, [email protected]
*
*
* Module containing a fast and space-efficient implementation of
* the Needleman-Wunsch algorithm. Extremely large alignments are
* partitioned using an expansion of the Hirschberg algorithm. Unlike
* the regular Hirschberg algorithm, gap-extend penalties are possible
* (this only requires a small sacrifice in space-scaling which is
* present in most implementations anyway). Also supports a quick
* method for finding an alignment score without the alignment itself.
*
* This package mainly serves as an alternative to pairwise2 from the
* Bio package, which runs much slower and runs out of memory rather
* easily. THIS PACKAGE KEEPS THE CONVENTION THAT INSERTIONS AND
* DELETIONS MAY NOT BE ADJACENT, THERE MUST BE AT LEAST ONE MATCH
* OR MISMATCH BETWEEN THE TWO.
*
*
* "score" returns the best global alignment score, not an alignment.
*
* "align" returns a global alignment and score, partitioning very
* large alignments.
*
* "qalign" is as align, but without partitioning. May run out of
* memory for very large inputs.
*
*
* Installation:
* python setup.py install
*
* Usage:
* import FastNW
* FastNW.method(string1, string2, match, mismatch, gap)
* FastNW.method(string1, string2, match, mismatch, gap, gap_extend)
*
*
* Future updates will allow for penalty matrices, non-integer
* penalties, and the option to perform local alignments.
* Additionally, extra error-checking will allow for the ability to
* recover gracefully from most memory errors. An option to return
* more than one optimal alignment is unlikely, as both time and
* space scaling guarantees are lost.
*
*
* Known bugs:
* 
* The Needleman-Wunsch algorithm currently uses ~2 times as much
* memory as it needs (still much less than other implementations)
* due to the matrix of scores being kept.
* 
* Partitioning currently must be exited early when a partition
* is of length 1 or 0. In very odd cases, this could lead to the
* program running out of memory.
*/