Sequence allignment with suffix array? I'm writing the code from scratch and not using libraries for the actual indexing/search since it's a project for school. Any blackbox advice is fairly useless.
I'm planning on aligning some short reads with the D. melanogaster genome but, since I was thrown into this project with very little info/ experience I'm stuck on a few things.
Firstly, for preprocessing the fasta file:

What should I do with Ns (ambiguous bases), I've seen some people removing them or replacing them by gaps but this does not seem like the same information? Should they be left in?

As far as I understand, the lowercase letters stand for potential repeats. However, If I just ignore this, it is possible my sequences might not align to the repeat because it is not actually stated as a repeat. E.g: &quot;ATATATAT&quot; will not align to 'at'.


As far as I understand the difference between using suffix array and suffix tree: suffix tree will search in linear time (but is memory intensive), while suffix array will be space efficient (but searches through ALL sequences each time). I'm leaning towards suffix array because I'm working on my laptop and memory is kind of limited. I'm also thinking that, since you sort the array lexicographically, you really only have to check the sequences if they start with the same first base as the read you're searching for?
Another question on the arrays: if my genome has 100M base pairs, the array will have 100M entries, some of them being close to 100M bases long? Should I be using the seed and extend method?
On the other hand, since the fruit fly genome is one of the smaller genomes, maybe it would be feasible to use a tree?
Is there any way to validate the alignment quickly at the end? How much error should I be allowing?
This were a lot of question, I've been trying to read up on things but I can mostly only find applications using biopython etc.
Any help would be hugely appreciated!
Suffix arrays vs Suffix tree is a problem quite often discussed in bioinformatics classes, but it's not that much used in practice. Most of people use already optimized mappers bowtie2 or bwa-mem.
I would advise you against your intention of mapping the reads using your own implementation of anything. You don't need to reinvent the wheel, just use an existing solution.
By the way, the Ns in the reference are either hard-masked nucleotides (that would be repeats of some sorts) or (more often) simply unknown nucleotides. So there is no way to map your reads there anyway (and the mentioned mappers will handle the Ns for you).