카테고리 없음

Finding a Motif in DNA(DNA에서 모티프 찾기)

곰탱이장 2024. 7. 21. 16:45

https://rosalind.info/problems/subs/

 

ROSALIND | Finding a Motif in DNA

It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Finding a Motif in DNA solved by 27629 2012년 7월 2일 12:00:00 오전 by Rosalind Team Topics: String Algorithms Combing Through the Haystack

rosalind.info

 이 문제는 DNA 가닥에서 모티프를 찾아내는 문제이다. 모티프란 분자생물학에서 특정 기능 혹은 특정 모양을 나타내는 특정 짧은 서열을 말한다. 예를 들어 어떠한 모티프는 특정 효소와 결합할 수 있게 하는 기능을 하는 식이다. 만약 다른 유전자나 DNA에서 그러한 모티프가 있다면 비슷한 기능을 한다고 추측할 수 있다. 

 문자열(N)에서 특정 문자열(M)을 찾는 알고리즘으로는 KMP 알고리즘이 있다. KMP 알고리즘이 시간복잡도가 O(N+M)으로 그냥 무식하게 구하는 O(N*M)보다 짧긴 하지만 구현하기에 복잡하다. 그러므로 필자는 그냥 무식하게 구하는 법으로 답을 찾아냈다.

seq=input()#DNA
motif=input()#모티프

seqL,motifL=len(seq),len(motif)
li=[]

for a in range(seqL):
    if seq[a:a+motifL]==motif:#무식하게 하나씩 비교
        li.append(a)

for b in li:
    print(b+1,end=' ')