First of all, this is not a question about alignment, but more about string matching/searching, but it might be related.
My problem is in the following image, but I don't know what's its name.
The problem is defined as follows:
Input: string P length m, string T length n (P is a short sequence, N is a long genome)
Algorithm: for each position i in [0..n-m], compute res[i] = sum(P==T[i:i+m])
In other word, res[i] = the number of equal characters between P and T[i:i+m]
Output: array res[i]
Does anyone know the name of this problem? Or is it never used anywhere?
If it is used, then what's the current method to calculate res[] ?
Thank you.
Oh, so it doesn't have an unique name :\
So in case I want to compute the min(res[]) (instead of the full res[i]), which method can I use?
The minimum of that score would be the maximal Hamming distance.
There is a concept called maximal Hamming distance under rotation, that sounds more like what you have with some caveats:
Thanks! I will look into that