Consider replacing Gotoh alignment algorithm

[donkirkby]

As I've been working on #549 to add support for SARS-CoV-2 references, I've had some trouble with running out of memory. I think it's partly that I'm running on equipment with less memory than I usually use, and partly that the SARS-CoV-2 genome is longer than HIV or HCV. The specific step that I've had most trouble with is aligning two consensus sequences using our Gotoh algorithm, so maybe it's time to look at alternatives.

@jeff-k had suggested we move from Gotoh to BWA, and that project seems to have been superceded by minimap2. Experiment with these tools for aligning the SARS-CoV-2 consensus sequences, and then decide whether they are worth switching to.

Tasks

• Switch genome coverage plot from Gotoh to minimap2 (Look for large deletions when aligning contigs #480).
• Use the same minimap2 alignment to clip out gene regions. Tracked in issue Make coverage maps consistent with contigs coverage plot #479.
• Review other uses of Gotoh, and decide whether they should be switched.

[donkirkby]

First impressions of minimap2:

• Good - it includes a Python wrapper and installs with pip. Nice!
• Not so good - any error conditions cause a None return value instead of raising an exception.
• Good - alignments seem to work as expected.
• Good - memory usage at least 100 times less for the current task.

[jeff-k]

For local alignment of two long consensus sequences, assuming one of them spans a range of the other (amplicon vs. reference), Smith-Waterman or Gotoh are sound choices. I have never used minimap2, but maybe the PacBio or Nanopore features for handling long reads would approximate this use case. I don't know what else those features would do, though.

At 30k bp, SARS-CoV-2 is going to stress a SW implementation that builds an entire N x M backtracking matrix. A useful optimization for SW space complexity is banding.

The rust-bio library has a good API for this: https://docs.rs/bio/0.20.3/bio/alignment/pairwise/banded/index.html which would be a good test bed for working out the alignment parameters.

[Donaim]

Working on #1221 I found that Biopython's default aligner is both faster and yields higher quality alignments.
Gotoh is still used in places where we expect a global alignment, which is where minimap is not so great.
But Biopython's aligner can totally replace gotoh there.