1

Say I have a list of 50 DNA sequences all of the same length (6, 8 or 16 bps/ chars).

I want to group these to sets of say 5 or 6 sequences per set. I have some criteria that need to be met based on the sequence:

1) There has to be at least three mismatches (different characters), 

ACGTAC
ACTTAT

has 2 mismatches - positions 3, and 6 , so would not meet the criteria

2) if we say A and C are red C and T are green (the laser colours on the sequencing machines), then we must have a green and red laser in each position. 

ACACTG
AATGAC
CCATGC

is equivalent to (r is RED, g is green)

RRRRGG
RRGGRR
RRRGGG

So the last four positions match the criteria (we have a red and a green in each position), but the first two positions are all red, so this set would not meet the criteria.

I have tried brute forcing this, and it works, but after the set size gets big enough, the number of combinations needed to check gets huge. So would this be a suitable task for some "machine learning" algorithms. Is there a type of algorithm / process that I should be looking at in particular?

(I just started a Coursera course, but the problems being discussed just now are linear regression, which seems to be a different class of problem).

Improve this question

1 Answer 1

Reset to default
2

There are lots of different algorithms that get classified as machine learning, but most of them have the flavor of "discover the imperfect pattern in the noisy data". It sounds like you already have an exact pattern, and you just want to count how many instances of it are in your data. That sounds like more like a combinatorics problem.

Improve this answer
2
  • +1. If the problem had simply stopped at, "Try to make clusters of similar DNA", then yes to machine learning (KNN or self organizing maps might provide some interesting starting points). But you are also trying to satisfy some hard constraints and it sounds like you want a specific, known optimal solution, so no. Perhaps posting a question on how to do what you're asking efficiently on one of the stackexchange family of sites might help?
    – J Trana
    Jun 29, 2014 at 3:57
  • I already did a fair bit of research into algorithms, but brute force seems to be the way.
    – wobbily_col
    Jun 29, 2014 at 21:55

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.