1
$\begingroup$

I have a project I'm working on where I'm trying to efficiently compare sequences of binary data to determine how similar they are. Basically, a sequence might look like this: 1001010010100011110...

I spent a while on my own trying to come up with a way to do it because it's fun for me to work through problems like this on my own, and actually made some progress. Unfortunately, everything I came up with never quite worked; a solution that accounts for substitutions (bits that flip) is easy, but what keeps getting me is handling bits that are inserted or deleted, i.e.: 100101 -> 1000101

Trying to find a solution online keeps leading me here, and I keep coming across the term cross-correlation. I also see lots of interesting links on the wikipedia page for Time Series for calculating similarities. Unfortunately, at the moment, a lot of the math is unclear to me, and I can't efficiently go through and distinguish what the appropriate technique might be for my situation.

So I have two different approaches to my problem that I'm interested in learning about:

1) What method would you recommend for calculating the similarity between two bit sequences (typically 50 to 150 bits in length) that is robust to substitutions, insertions, and deletions?

2) I'm not sure this is possible, but is there some kind of distance metric(s) I can calculate independently for each signal that will allow me to group them together with actually doing direct pairwise comparisons?

For 1, I feel like cross-correlation might be the right approach, but I haven't gotten past just plugging sequences in R and seeing how it works for identifying lag. I know edit distance will work, but ultimately will want something more efficient. Eventually, I will be trying to group billions of these together.

Thanks

$\endgroup$
  • $\begingroup$ Have you looked at en.wikipedia.org/wiki/Levenshtein_distance? $\endgroup$ – MBaz Dec 2 '15 at 22:42
  • $\begingroup$ I've come across it in bioinformatics where it's used to compare genetic sequences, but I was hoping that because my data is purely numeric and simpler than the case of comparing character strings, that there is a more direct mathematical approach. Ultimately, I think I could adjust that method to be more efficient for my particular case, but I'm less sure that I will be able to adapt it for use in GPGPU computing using OpenCL, which is my goal down the line. $\endgroup$ – anjama Dec 3 '15 at 3:04
1
$\begingroup$

You should indeed look into sequence alignment methods used in bioinformatics. Those can penalize both for insertions/deletions and mismatches. The binary alphabet having a size of 2 and that of DNA having a size of 4 does not require the use of different algorithms if the element-wise comparison results in either "match" or "mismatch", and a mismatch is penalized for. Check out the Needleman–Wunsch algorithm, which is based on dynamic programming.

Some DNA/protein sequence alignment algorithms such as MAFFT use Fast Fourier Transform (FFT) for accelerated cross-correlation of residue properties to approximate match calculations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.