마지막 게시물 직후부터 준비를 포함하여 많은 일이 진행되고 있습니다. JMP 16 , 불과 며칠 전에 나온 글인데, 독자들이 겪었던 칼럼 수식 문제를 묻는 지난 게시물에 대한 답변이 없어서, 시간을 들여 읽을 가치가 있는 글을 게시할 시간이나 자료가 없다고 생각했습니다.
요즘 시간이 조금 더 생겨서 새로운 도전이 필요한 시기입니다. 칼럼 수식 과제는 나중에 정리하고 새로운 과제와 새로운 접근 방식으로 시작하겠습니다. 이 게시물과 그 이후에 몇 가지에 대해 이야기하겠습니다. 커뮤니티 게시물에 대한 Craige Hales의 답변을 기반으로 한 일반적인 질문입니다. . 크레이지( @Craige_Hales )는 JMP Development에서 은퇴했음에도 불구하고 여기 커뮤니티에서 매우 활발하게 활동하며 사용자 질문에 답변하고 미지의 블로그 , 그리고 이 블로그에 기여하고 있습니다. 문제는 루프를 사용하지 않고 (다차원) 목록을 전치하는 효율성에 관한 것이었습니다. 저는 제가 자주 궁금해했던 좀 더 일반적인 질문을 던지고 싶습니다. "반복에 대한 더 나은 대안이 있습니까? 그렇다면 그것은 무엇입니까?" 대부분의 경우 더 좋다는 것은 더 빠르다는 것을 의미하지만, 속도가 너무 많이 저하되지 않는다면 코드 압축도 고려할 것입니다. 또한 차이점이 있는지 확인하기 위해 반복에 대한 다양한 접근 방식을 살펴보겠습니다. 텍스트 검색부터 시작해 보겠습니다.
문자열
생물정보학의 일반적인 작업은 특정 하위 문자열 패턴을 찾기 위해 유전 정보가 포함된 문자열을 검색하는 것입니다. DNA의 경우 문자열 문자는 A, T, C, G의 네 글자로만 구성됩니다. 파일 코비드19.TXT (이 게시물에 첨부됨)에는 약 30,000자 길이의 코로나19 게놈에 대한 유전자 서열이 포함되어 있습니다(반면, 가장 긴 인간 염색체 1번의 길이는 약 2억 9천만 자입니다). 2~10자 길이의 특정 하위 문자열이 모두 나타나는 위치를 찾기 위해 얼마나 빨리 검색할 수 있습니까?
네 가지 접근 방식을 살펴보겠습니다. 그 중 세 가지는 반복적입니다. 기술에 관계없이 하위 문자열 일치가 겹칠 수 있다는 점에 유의하세요. 예를 들어, BAB 2번 들어있어요 바밥 , 위치 1에서 3까지, 다시 3에서 5까지입니다. 우리는 이 두 가지 사건을 모두 포착할 무언가가 필요합니다. 우리는부터 시작하겠습니다 하위 문자열 아래 코드를 사용하여 문자열 검색할 문자열이고 inSeq 검색할 하위 문자열입니다.
findSequence = Function({inString,inSeq},{i,seqLen,checkTo,outVec},
seqLen = Length(inSeq);
checkTo = Length(covid19)-seqLen+1; //Only need to go until the substring includes the last character
outVec = J(checkTo,1,0);
For(i=1,i<=checkTo,i++,
outVec[i] = Substr(inString,i,seqLen) == inSeq;
);
Loc(outVec);
);
이는 하위 문자열 길이에 관계없이 평균 1.2초가 소요되는 접근 방식 중 가장 인상적이지 않았습니다. 결과는 아래와 같습니다(마이크로초 단위). 테스트에서는 각 하위 문자열 길이에 대해 10개의 무작위 하위 문자열을 생성하고 검색을 20회 반복했습니다. 주어진 길이의 모든 하위 문자열에 대해 값이 요약되었습니다. 개별 하위 문자열에 대한 자세한 내용은 코비드 19 결과 Full.JMP 이 게시물에 첨부되었습니다. 테스트를 생성하는 데 사용된 코드는 Test Covid19 Search.JSL에 있습니다.
| 하위 문자열 길이 |
하위 문자열 |
색인 |
포함 |
PatMatch |
| 2 |
1,227,342 |
60,312 |
79,640 |
4,046 |
| 삼 |
1,245,909 |
62,650 |
22,143 |
3,103 |
| 4 |
1,215,641 |
66,045 |
4,938 |
2,881 |
| 5 |
1,218,983 |
72,337 |
1,293 |
2,880 |
| 6 |
1,220,846 |
76,705 |
357 |
2,956 |
| 7 |
1,249,843 |
77,127 |
234 |
3,010 |
| 8 |
1,212,982 |
84,413 |
132 |
3,078 |
| 9 |
1,227,892 |
87,479 |
113 |
3,331 |
| 10 |
1,208,948 |
89,732 |
106 |
3,742 |
우리는 이전 과제에서 다음을 확인했습니다. 하위 문자열 느립니다. 문자열을 "원자화"하여 개별 문자로 나누고 문자 범위를 살펴본다면 어떻게 될까요? 이에 대한 동기는 C와 같은 언어에서 가능한 것처럼 인덱싱을 통해 문자열 값에 직접 액세스하는 순서입니다. 문자열을 직접 인덱싱할 수 없기 때문에 JSL에서는 원자화 부분이 필요합니다. 내가 사용한 코드는 다음과 같습니다.
findSequence = Function({inString,inSeq},{i,seqLen,checkTo,outVec,inList,seqList},
seqLen = Length(inSeq);
checkTo = Length(inString)-Length(inSeq)+1; //Only need to go until the substring includes the last character
outVec = J(checkTo,1,0);
inList = Items(inString,"");
seqList = Items(inSeq,"");
For(i=1,i<=checkTo,i++,
outVec[i] = inList[i::(i+seqLen-1)] == seqList;
);
Loc(outVec);
);
이 접근 방식은 검색된 문자열을 검색하는 것 외에도 검색된 문자열을 분할하는 초기 오버헤드가 있기 때문에 시간이 더 많이 걸릴 것처럼 들리지만 결과 테이블에서 볼 수 있듯이 약 13-19X 더 빠릅니다. 같지 않은 하위 문자열 그러나 검색 시간은 하위 문자열 길이에 따라 증가합니다.
최종 반복 접근 방식은 다음을 사용합니다. 포함 . 아이디어는 주어진 부분 문자열을 찾고, 검색된 문자열에서 해당 위치를 표시하고, 부분 문자열을 찾을 수 없을 때까지 해당 위치를 지나 한 문자부터 시작하는 프로세스를 반복하는 것입니다. 이 방법의 매력은 검색된 문자열에서 하위 문자열이 거의 발생하지 않을 때 검색 속도가 매우 빨라진다는 것입니다. 아래 코드는 Brady Brady( @brady_brady 
findSequence = Function({inString,inSeq},{pos=0,ans={}},
while(1,
pos = contains(inString, inSeq, pos);
if(pos, insertinto(ans, pos++), break())
);
ans;
);
보시다시피, 이 접근 방식은 두 문자 하위 문자열에 대한 인덱싱 방법보다 약간 느리게 시작되지만 하위 문자열이 길어질수록, 즉 찾을 하위 문자열이 적어질수록 속도가 급격히 빨라집니다.
마지막 접근 방식은 내가 가장 좋아하는 JSL 도구 중 하나인 패턴 일치를 사용합니다. 코드가 빠를 뿐만 아니라 짧습니다.
findSequence = Function({inString,inSeq},{i=1,locs={}},
Pat Match(inString,Pat Pos()>>r + inSeq + Pat Test(Insert Into(locs,r+1);0));
locs;
);
2문자 하위 문자열의 경우 약간 느리지만 3자 이상의 하위 문자열 길이에는 영향을 받지 않는 것 같습니다.
분명히, 다음을 사용하는 반복적 접근 방식은 포함 패턴 일치 접근 방식은 긴 문자열을 검색하는 데 탁월한 방법입니다. 하지만 어떤 방법으로, 언제? 테스트는 다른 하위 문자열을 사용하여 수행되었으므로 하위 문자열 빈도(발생 횟수*1000/29,903)가 검색 시간에 어떤 영향을 미칠 수 있는지에 대한 일부 표시가 있습니다. 아래 플롯은 1,000자당 2개의 하위 문자열 빈도 근처의 교차점을 보여줍니다. 그러나 모든 테스트는 동일한 covid19 게놈 문자열에서 수행되었기 때문에 검색된 문자열 길이가 검색 시간에 어떤 영향을 미치는지는 불분명합니다.
이러한 질문에 대한 답을 찾고 요인 간의 가능한 상호 작용을 탐색하기 위해 검색된 문자열 길이(10,000~500,000자), 하위 문자열 길이(2~21자) 및 빈도( 0.75 – 1,000자당 하위 문자열 3개). 소수 문자열 길이 값을 반올림한 Fast Flex 설계를 사용하여 125개의 실행이 생성되었습니다. 각 실행에 대해 임의의 알파벳 문자 문자열이 생성되었습니다. 해당 문자열 내에서 무작위로 생성된 숫자로 구성된 하위 문자열이 임의의 위치에 삽입되었습니다. 빈도 값은 정수가 아닌 삽입 횟수로 이어질 수 있으므로 삽입 횟수는 빈도의 최대값에 검색된 문자열 길이를 1,000으로 나눈 값을 곱한 값으로 간주되었습니다. 각 실행은 동일한 검색된 문자열/하위 문자열 조합에 대해 10번 반복되었습니다. 실행을 생성하는 데 사용되는 코드는 다음과 같습니다. 디자인 스크립트 실행.JSL 결과는 공간 채우기 결과 1.JMP 이 게시물에 첨부되었습니다.
결과를 빠르게 살펴보면 13개의 관찰 결과만 표시됩니다. 포함 메서드가 패턴 일치보다 성능이 뛰어납니다. 이 중 가장 큰 차이는 약 4,000마이크로초 더 빠르다는 점입니다(반면 패턴 매칭은 0.72초 더 빨랐습니다). 포함 ). Gaussian Process 모델을 데이터에 맞추는 것은 검색된 문자열 길이가 검색된 문자열 길이 상호작용에 의해 강한 빈도로 가장 큰 영향을 미쳤음을 시사합니다. 하위 문자열 길이는 거의 영향을 미치지 않았습니다. 처음에는 선형 모델이 데이터에 적합했지만 잔차 분석에서는 적합성이 의심스러울 수 있음을 시사했습니다. 나는 게시했다 이 모델과 후속 모델을 위한 대화형 프로파일러 버전 JMP 공개로.
두 번째 공간 채우기 디자인은 다음과 같은 경우를 더 잘 표현하기 위해 만들어졌습니다. 포함 패턴 매칭보다 성능이 뛰어납니다. 이 실험에서는 두 현 길이의 범위가 이전과 동일하게 유지되었으며 주파수는 0과 1 사이에서 변경되었습니다. 결과는 공간 채우기 결과 2.JMP . 결과의 방향은 검색된 문자열 길이가 길고 패턴 일치를 선호하는 빈도가 높아 이전과 유사했습니다.
두 결과 세트를 결합하고 Gaussian Process 모델을 피팅하면 50,000자의 문자열에 대해 다음이 제안됩니다. 포함 주파수가 2 미만이면 더 우수합니다. 100,000자에서는 빈도가 1로 떨어지고 200,000자에서는 0.5 미만으로 떨어집니다. 이것의 결론은 더 짧은 문자열의 경우 다음을 사용한다는 것입니다. 포함 문자열 길이와 밀도가 증가함에 따라 패턴 일치가 더 우수해집니다.
이달의 도전
코로나19 게놈을 사용하여 두 번 이상 나타나는 가장 긴 부분 문자열을 찾습니다.
다음 게시물까지 이에 대한 답변을 남겨두기보다는 토론하고 공유해 봅시다. 나는 이것이 매우 어려운 문제라고 생각하며 공개 토론을 통해 이익을 얻을 수 있습니다.
어떤 상황에서는 더 나을 수도 있고 그렇지 않을 수도 있는 다른 접근 방식을 찾아보십시오(확인할 시간이 없었습니다).
NamesDefaultToHere(1);
str = LoadTextFile("$DOWNLOADS/covid-19.txt");
txt = "AACA";
bStr = CharToBlob(str);
bTxt = CharToBlob(txt);
pos = {};
for(i=1, i<=(Length(str) - Length(txt)), i++,
if(BlobPeek(bStr, i, Length(txt)) == bTxt, InsertInto(pos, i+1));
);
Print(NItems(pos));중복도 포함인가요? 그러면 쉽습니다. 그래도 겹치는 부분을 제외하고 어떻게 할 것인지 잘 모르겠습니다. 이 솔루션은 제공된 데이터에 대한 5~10초 답변입니다. 그리고 훨씬 더 긴 하위 문자열이 포함된 훨씬 더 긴 데이터의 경우 고통스럽습니다.
아이디어는 텍스트의 모든 위치 1...길이에서 서로 다른 부분 문자열 길이에 대해 발생하는 각 부분 문자열의 수를 계산하는 것입니다. 그런 다음 "1보다 큰 개수가 있습니까?"라고 질문합니다. 하위 문자열 길이에 대한 이진 검색을 사용하여 중복을 생성하는 가장 큰 하위 문자열 길이를 찾습니다. 동일한 길이의 더 흥미로운 다른 하위 문자열이 있는지 확인하려면 마지막에 좀 더 작업을 수행해야 합니다.
txt = Load Text File( "z:/covid-19.txt" );
// finding the longest duplicated substring, including overlaps.
// if there is one, then there will be shorter ones of every possible
// shorter length. So, as the possible length of the substring grows,
// there is a boundary at some length where all shorter lengths have
// duplicates and no longer lengths have duplicates. find the boundary.
// do a binary search for the longest string that occurs 2 or more times
// testlength is the length during a pass
// see https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure
// for a *real* binary search. this code is potentially wrong and very
// poorly tested!
// Changing the maxlength guess below from 1...1000 will produce different times.
// 20 is a good starting point, bigger than 200 or so is very slow because
// length(txt) * maxlength strings are being manipulated, a lot.
start = Tick Seconds();
minlength = 1;
maxlength = 27; // initial guess, will (slowly) auto-adjust bigger as needed
firstpass = 1; // needed to detect guess too small
minkey = .;
minval = .;
while( 1,
testlength = if( firstpass == 1,
Min( Length( txt ), maxlength )// this binary search starts at the big end, then splits on subsequent passes. This lets code
, // else
Floor( (minlength + maxlength) / 2 )// below test that the big end is big enough on the first pass.
);
Write( "testing strings of length ", testlength, "\!n" );
Wait( 0 );
aa = [=> 0];
patmatch( txt,
Pat Len( testlength ) >> sequence + //
pattest( // build the associative array of key=sequence, val=count
aa[sequence]++;
// usually I use 1; on the next line. that always succeeds.
// here, I want pattest to make the matcher back up and retry...
0; // fail! try again at next position
),
NULL, // unused positional replacement
FULLSCAN // needed to bypass a heuristic and get the last little bit
);
keys = aa << getkeys;
vals = aa << getvalues;
idx = Loc Max( Matrix( vals ) );
bigN = vals[idx];
//
// the binary search is for the biggest testlength that has bigN > 1.
// bigN is the maximum repeats of a string of testlength characters.
//
if( bigN == 1,
maxlength = testlength;// maxlength promises to be 1-too-big at the end
, //else
minlength = testlength;
Write( " found some, minlength=", minlength, " maxlength=", maxlength, "\!n" );
minkey = keys[idx];
minval = vals[idx];
if( firstpass == 1, // looking for a big-enough high end, still
maxlength = Min( 2 * maxlength, Length( txt ) );
Write( "Increasing max, minlength=", minlength, " maxlength=", maxlength, "\!n" );
Continue();
);
);
firstpass = 0;
if( minlength >= maxlength - 1,
if( Is Missing( minkey ),
Continue();// needs one more pass
, // else
Break();// got it
)
);
);
Write( "\!n", minkey, " occurs ", minval, " times at " );
patmatch(
txt,
Pat Pos() >> location + //
minkey + //
pattest(
Write( location + 1, " " );
1;
) + //
Pat Fail() // this will also retry the match, 1 character further along
);
Write( "\!n" );
stop = Tick Seconds();
Show( stop - start );
Contains 접근 방식은 아래와 같이 더 간결하게 작성할 수 있습니다. 비교가 제거되면 조금 더 빠르게 실행된다는 이점도 있는데, 특히 하위 문자열이 기본 문자열 내에 존재하지 않을 때 가장 두드러집니다.
findSequence = Function({txt, sub},{pos=0,ans={}},
while(pos = contains(txt, sub, pos), insertinto(ans, pos++));
ans;
);
