Kalenderluke 8: To DNA-sekvenser


søndag 8. desember 2013 Julekalender

luke8_stillingen

Luke 8 ser ut til å ha vært den vanskeligste luken sålangt i kalenderen. Terje Tjervaag fra Bouvet klarte likevel å løse den 2 minutt og 33 sekunder. Magnar brukte 4 minutter og 39 sekunder, og beholder dermed ledelsen sammenlagt.

Oppgaven gikk ut på å finne den lengste sammenhengende rekken med nukleinsyrer som var felles i to DNA-sekvenser. Det korrekte svaret var TACTTCGATCG. Dette problemet er kjent som Longest Common Substring, og du finner løsninger i mange språk på nettet. Her er en implementasjon i Ruby:

def find_longest_common_substring(s1, s2)
  return if (s1 == "" || s2 == "")
  m = Array.new(s1.length){ [0] * s2.length }
  longest_length, longest_end_pos = 0,0
  (0 .. s1.length - 1).each do |x|
    (0 .. s2.length - 1).each do |y|
      if s1[x] == s2[y]
        m[x][y] = 1
        if (x > 0 && y > 0)
          m[x][y] += m[x-1][y-1]
        end
        if m[x][y] > longest_length
          longest_length = m[x][y]
          longest_end_pos = x
        end
      end
    end
  end
  return s1[longest_end_pos - longest_length + 1 .. longest_end_pos]
end

Nå ser det ut som om de på toppen begynner å få et solid forsprang. Men husk at lukene blir mere og mere verdt for hver dag som går. Dessuten kommer flere av lukene som er igjen til å være krevende, og gjør f.eks. Magnar en feil så er det ikke så veldig vanskelig å ta ham igjen.


comments powered by Disqus