오늘도 뭔가를 만들다가, 아미노산을 문자열에 쭉 입력해 놓고, 숫자를 세 보고 20개 맞군! 하고 지나가면서 뭔가 “이걸 문장을 만들어서 외워 놓으면 맨날 하나 하나 생각하면서 20개 맞나 세 볼 필요가 없지 않을까!” 하는 생각에 아미노산을 모두 1번 씩 쓰는 문장을 만들면 정말 재미있겠다는 생각을 했습니다. 마치 폰트셋 볼 때 잽싼 여우가 게으른 개를 뛰어 넘는 것 같이 말이죠~ –; 그냥 ‘ACDEFG…VWY’를 메모 프로그램에 적어두거나 모듈로 만들어 저장해 둬도 되겠지만, 이미 재미있는 놀이가 생각난 판에, 다른 좋은 방법이 눈에 들어오지 않았지요;
결과만 올리면 너무 오래 뻘짓만 한 것 같아서 과정을 상세히 써 봅니다. -O-;;
우선 단어 후보를 한번 추려보기로 했습니다. FreeBSD에서 항상 뭔가 장난할 때 쓰이는 webster 단어 목록을 써서 추려봤습니다. 우선 다 읽어서, 아미노산 알파벳만 쓰고 있는 단어를~
|
1 2 3 4 |
>>> words = open('/usr/share/dict/web2').read().split() >>> aa = 'acdefghiklmnpqrstvwy' >>> m = re.compile('^['+aa+']+$') >>> words = [w for w in words if m.match(w.lower())] |
한 단어에 같은 알파벳이 들어있다거나, 너무 짧거나 너무 긴단어를 뺐습니다.
|
1 2 3 4 |
>>> words = [w for w in words if len(set(w.lower())) == len(w)] >>> words = [w for w in words if 2 <= len(w) <= 7 or w in 'Ia'] >>> len(words) 9863 |
지금까지 걸러낸 조건에 맞는 단어가 9863개가 있군요~ 뭔가 나올 것 같아서 벌써 기분이 좋습니다 ㅎㅎ;
자 이제 겹치지 않는 단어를 골라야하는데, 각각의 알파벳이 중복되지 않게 조합하는 문제이기 때문에, 정수계획법 (IP)으로 간단하게 풀릴 것 같아서, glpk로 안 겹치는 조건을 프로그래밍 했습니다.
|
1 2 3 4 5 6 7 8 9 |
set W; /* Words */ set A; /* Alphabets */ param aw{W,A}, integer; /* # alphabets in each word */ var used{w in W} >= 0, integer; /* words selected */ s.t. alphasmin{a in A}: sum{w in W} aw[w,a] * used[w] >= 1; minimize aused: sum{a in A} sum{w in W} aw[w,a] * used[w_]; end; |
이제 아까 골라낸 파일에서 데이터를 glpk에서 읽을 수 있게 변환~
|
1 2 3 4 5 6 7 8 9 10 11 |
>>> import sys; sys.stdout = open('data.txt', 'w') >>> print 'set W :=', ' '.join(words), ';' >>> print """\ ... set A := %(aas)s; ... param aw default 0 ... : %(aas)s :=""" % {'aas': ' '.join(aa)} >>> for w in words: ... wlow = w.lower() ... print w, ' '.join(str(int(a in wlow)) for a in aa) ... >>> print ";\nend;" |
자 그럼 이제 준비가 다 되었으니 돌려봅시다 -ㅇ-
|
1 2 3 4 5 6 7 |
% <b>glpsol --first -m solword.mod -d data.txt -o found.txt</b> Reading model section from solword.mod... (중략) INTEGER OPTIMAL SOLUTION FOUND Time used: 1.0 secs Memory used: 37.2M lpx_print_mip: writing MIP problem solution to `found.txt'... |
으흐흐.. 결과가 나왔군요! (사실은 나오는 데 꽤 걸렸지만 제약조건 다 풀어서 처음 나온 것이 바로 feasible solution이 나온 척 해 봅니다; )
자.. 이제 결과를 해석해 보면.. 단어가 cwm fed glyph qintar skiv 라는군요.. (덜덜덜) 아미노산이 모두 들어있기는 하지만.. 과연 이게 철자 검사기를 통과하기나 할까 싶은 단어들이 막 나오는군요.. 으흐.. webster 단어들은 대단해~ 이걸 뭔가 좀 쉬운 단어들로 바꿔서 해 보고 싶지만, 쉬운 단어를 골라놓은 사전을 쉽게 찾을 수가 없어서 일단은 여기서 중단; 자.. 이제 저걸 외워볼까요 glyph fed cwm qintar skiv~ (곡도 붙여서..) 흑흑흑..
앞의 결과는 너무 쓸모없는 것 같아서 –; 다른 데 하나 응용해 봤습니다. 해리포터에 보면 Tom Marvolo Riddle이름이 볼드모트로 바뀌는 장면이 있길래, 볼드모트랑 철자 구성이 같은 놈을 하나 만들어 보니까.. dom revolt가 나오는군요.. 역시 짧으니까 그다지 문장으로 만들 수가 없는.. 크흐..
오늘의 결론: 여우가 게으른 개 위로 뛰어 넘는다는 문장은 정말 대단하다!
재밌는 시도네요 🙂
오늘의 결론에 미투!
엉뚱한 질문입니다.
혹시 방금 만드신 문장과 동일한 순서(sequence)를 subsequence로 가지는 단백질이 있나요? (있다면 대박일 듯)
엉뚱한 질문에 동해 blast 를 가볍게 돌려봤습니다. 결론은 exact match 는 없더라 라는 것. 9개 뭐 이렇게 맞아떨어지는 녀석은 있지만, 전체 sequence 가 맞아떨어지는 건 존재하지 않는군요. (왠지 아쉽)
‘단어를 단순한 리스트가 아닌 ‘동사’,’명사’ 등의 정보를 담고 있는 리스트를 대상으로 해서, 문장의 구조를 포함해 문제를 풀게 하면 되지 않을까?’, ‘하나만 내뱉으면 의미있는 문장이 나올 확률이 거의 제로일테니 찾아낸 모든 해답을 토해내게 해야할건데, 좀 시간이 많이 걸리려나?’ 따위의 잡생각(?)에 잠시 불타올랐습니다만, 논문 쓰다말고 할 짓이 아니라서 포기했습니다 ㅠ.ㅠ
glpk라는 것, 잘 봤습니다. 써먹을 일이 생기면 참고해봐야겠네요. 흐흐;
퍼키님이 하신 장난에 호기심이 발동하여….
퍼키님이 하신 그대로 tracking을 하고 있습니다만 마지막 glpsol을 돌리는데서 문제가 있는데요. 에러는 아래와 같습니다. 버전이 틀려서 일까요? 제가 쓰고 있는 놈은 4.16입니다만..
Reading model section from solword.mod…
solword.mod:7: w_ not defined
Context: …d : sum { a in A } sum { w in W } aw [ w , a ] * used [ w_ ]
Model processing error
쓰고 계신 버전이 얼마인가요?
아~ 원래 썼던 변수명을 다른 걸로 바꾸는 과정에서 제가 하나 빼먹었네요.
w_를 w로 바꾸시거나 다른 w를 모두 w_로 바꾸시면 됩니다.
(원래 알파벳과 겹칠까봐 w_로 썼었는데, 안 겹치는 것 같아서 원래대로 바꾸는 과정에서 실수;;)
it.stlawu.edu/~ehar/FOS05/abstracts/forum/282741.html
it.stlawu.edu/~ehar/FOS05/abstracts/forum/694389.html
it.stlawu.edu/~ehar/FOS05/abstracts/forum/397569.html
it.stlawu.edu/~ehar/FOS05/abstracts/forum/971543.html