텍스트 중간에 서로 가깝게 반복되는 문자열 찾기

텍스트 중간에 서로 가깝게 반복되는 문자열 찾기

근처에 중복된 텍스트 파일이 있는 13자 문자열을 찾아야 합니다.
이는 게놈의 돌연변이를 의미합니다13.

예를 들어:

ACGAATTGCAGCCACAGTACGAATCGCAGCC.

ACGAATTGCAGCC로 시작하여 끝나지만 그 사이에는 길이를 알 수 없는 임의의 문자가 포함됩니다.

지금까지 내가 생각한 것은 다음과 같습니다.

grep -Eo '((.){13}).{1,100}\1'

이걸 찾아야 해

GTACCATAACTAACAACCTGAAAAGTCACAAAAACATATACAATAAAAGAACTAGATTTCGCATAGGATATATATTAATAAAGTGAACAAAAAAAAAATAACAACAACAACAACGAATGAAGAAAGGAAAAGGAATGATAAAAAAACGAGTAATAATTGAAAACAATTATAAAGTAAGAAAACCGCAACGGCCCAAGTAAGCAAAGCAAGGATAGGAAATTGATCGACACAACTCCATAAAATTTACAACTAGTACTCAGAAAAAATAACTAAGCTATATCCATATCTACTCTAAAAAAGAAAAGGAATAACGGAACACCCACAAAGAAACTCAATTAGCAAAAACCACAGATAATACAAACCAGAGAAGACCACATAAAAAAATGAACGAGTTACCCTTCAAATTAAAATAAATCTACCAGTAAGCATAAAAACAACAAAGTTACAAAACCAAAGACCAAAAGTAGAAATCAGAACAAGGGACATAAACGTTCACCAAATGAATGAAACAACACAATTTAGAAACAAAAAAGAGGAATAAAAAGCCAGAACAGGAGTACGAACATAATTAATTATGAAAGTGACCTACAAATAAGAAGGAAACACAAACAGAAAACAACTAACCACAAAAAAGACATAATAGTAAACAAAAAAAAAAAACTTACTCATACGAGGACTAATAAAAGATTCAAAACAATACAATTGACGAAAACTCAACGAGGAAAGCTAGAAAACCACCAGAGAAACTCAAAACACAAATAGAGATAAAAAAAAAAACCATAAAGAAAAATTCTTACATCGTCACAGCCAAGGAAAAAAAGAAATCGTTAAAATGGAACGCAGTCGAACACAAAAAGACAACACAGAACAAAAAAGGCAAACAGCGTAGAAACAAATACACTCGCGTAGCAAAGGGGCGGCGTCACGCTTGAAACATAAAAATAACCACTGTATATCACGACAATCAACAAAGTCTACATCAAGAAAATCAAAAAAATAC

답변1

꽤 가깝습니다. 문제는 100입니다. 너무 좁습니다! Posix Extended 대신 Perl PCRE 사용을 고려할 수도 있습니다. 성능 차이가 매우 눈에 띕니다.

grep -Po '((.){13}).{1,1000}?\1' genom
AACAAAAAAAAAATAACAACAACAACAACGAATGAAGAAAGGAAAAGGAATGATAAAAAAACGAGTAATAATTGAAAACAATTATAAAGTAAGAAAACCGCAACGGCCCAAGTAAGCAAAGCAAGGATAGGAAATTGATCGACACAACTCCATAAAATTTACAACTAGTACTCAGAAAAAATAACTAAGCTATATCCATATCTACTCTAAAAAAGAAAAGGAATAACGGAACACCCACAAAGAAACTCAATTAGCAAAAACCACAGATAATACAAACCAGAGAAGACCACATAAAAAAATGAACGAGTTACCCTTCAAATTAAAATAAATCTACCAGTAAGCATAAAAACAACAAAGTTACAAAACCAAAGACCAAAAGTAGAAATCAGAACAAGGGACATAAACGTTCACCAAATGAATGAAACAACACAATTTAGAAACAAAAAAGAGGAATAAAAAGCCAGAACAGGAGTACGAACATAATTAATTATGAAAGTGACCTACAAATAAGAAGGAAACACAAACAGAAAACAACTAACCACAAAAAAGACATAATAGTAAACAAAAAAAAAA

내 컴퓨터의 시간 비교:

Posix: (-E)  0m4.816s
Perl:  (-P)  0m0.011s

관련 정보