**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

Not sure why we're not getting 100% identity when the minimum%Overlap is 1.0. They should be doing the same thing at that point. 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?