**This is an old revision of the document!**

# Alignment

We have implemented a NW-alignment algorithm in Java. We then implemented a banded NW-aligner. We then optimized the banded NW-aligner to run in linear space.

minimum%Overlap	band_noband_identity	unbandedTime		bandedTime	linearBandTime
0.2		0.982			2.812			1.5482		1.8109
0.4		0.989			2.8063			2.4472		2.9774
0.6		0.993			2.7984			3.1182		3.4305
0.8		0.994			2.822			3.547		3.3106
1.0		0.996			2.7969			3.6476		2.8028
1.0		1.0			2.9273			3.3881		2.9144

I think that we're not always getting 100% identity when the minimum%Overlap is 1.0 because of floating point precision issues. I reran setting the minimum%Overlap to 1.0 exactly and it had perfect identity. There is also always perfect identity between the two banded.

Need to graph them. Turns out banding doesn't necessarily save us a ton of time. Too much bookkeeping? Not long enough sequences to see a payoff?