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

minPercOverlap	banded_identity	band_noband_identity	unbandedTime	bandedTime	optimizedBandTime	totalAlns
0.03125		1.0		0.893			3.0931		0.7097		0.4767			225.0
0.0625		1.0		0.956			2.9003		0.8283		0.5601			225.0
0.125		1.0		0.9734			2.94		1.1837		0.9215			225.0
0.25		1.0		0.9867			2.925		1.8431		1.569			225.0
0.5		1.0		1.0			2.9287		2.9216		2.493			225.0
1.0		1.0		1.0			2.9299		3.8145		2.5307			225.0

Initially the optimizedBandTime was running quite a bit slower. I greased it up by minimizing repetitive calculations and now it seems to be working faster than the unbanded aligner even when the “band” is the full sequence length. It's interesting to see that with the minimum percent overlap at 50%, the banded alignment still finds the same alignment as the unbanded 100% of the time. These results are exact character matching by the way, and I imagine those numbers will go up slightly if we change everything to lowercase:

minPercOverlap	banded_identity	band_noband_identity	unbandedTime	bandedTime	optimizedBandTime	totalAlns
0.03125		1.0		0.8978			2.9952		0.7033		0.4429			225.0
0.0625		1.0		0.96			3.0146		0.869		0.5882			225.0
0.125		1.0		0.98			2.924		1.1947		0.9135			225.0
0.25		1.0		0.9867			2.9173		1.8567		1.576			225.0
0.5		1.0		1.0			2.9185		2.996		2.5493			225.0
1.0		1.0		1.0			2.9427		3.925		2.6588			225.0

Interesting that the band_noband_identity went up slightly, but only for smaller bands. What this means is that there are some cases where case makes a difference, but with sufficiently large context, it figures it out anyway. Also keep in mind that the listed times are for all 225 alignments. The per alignment time is thus on the order of .012 seconds. Also the times are averages of 10 iterations.

LDAP: couldn't connect to LDAP server
mind/alignment.1463165327.txt.gz · Last modified: 2016/05/13 12:48 by norkish
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0