- 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: "ATATATAT" will not align to 'at'.
Good questions. I think this depends on the scope of your class project. Frankly, I think it would be best to just start with unambiguous sequences (only ATGC) and not worry about potential repeats. It's also a good software engineering exercise to solve the easy case first in a way that's flexible and allows you to expand to the additional complexities above. For example, the original Bowtie software considered references with ambiguous characters invalid. You can see for yourself here how Bowtie2 handles it.
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?
Yes, the most naive implementation of a search with a suffix array will be $O(m\log n)$ time, where $m$ is the read length and $n$ is the genome length. However, with enhanced suffix arrays you can also obtain the same $O(n)$ search complexity of suffix trees. There is also the use of suffix arrays to construct Burrows-Wheeler transforms and even further compression with the FM index. There are open source implementations of all of these data structures that may be interesting to you.
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?
Suffix arrays store the indices of the start of each suffix in order to save space, so each entry is a single integer.
On the other hand, since the fruit fly genome is one of the smaller genomes, maybe it would be feasible to use a tree?
Its worth trying to compute this yourself (: You can determine the number of bytes required per base pair in your input and see how that scales with your available memory. For example, if your suffix tree implementation required $20n$ bytes, you'd end up w/ roughly 2Gb needed for a fruit fly genome.
Is there any way to validate the alignment quickly at the end? How much error should I be allowing?
Again, this depends on the scope of the project. Allowing for errors in mapping reads is an active area of research. See the supplemental of the Bowtie2 paper for a dynamic programming algorithm that handles a certain number of mismatches.
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.
All good questions, and I think many answers depend on the scope of the project. Reimplementing a read mapper is no small feat, especially when you start considering all of the different complexities such as sequencing error and ambiguous bases. I would strongly consider starting with looking at just the pure string problem of read mapping: Only consider ATCG in both reference and reads, and don't even consider reads who do not have exact matches to the reference. From there, time permitting, you can start adding on to your solution. As far as reading goes, there's a deep rabbit whole of these topics, from tools like bwa-mem, bowtie2, mini-map, to the more theory-oriented papers discussing optimized versions of the data structures. I can attach some here if you would like. Hope these answers helped!
