마지막 게시물 직후부터 준비하는 것을 포함하여 많은 일이 진행되고 있습니다. JMP 16 , 불과 며칠 전에 나왔고 독자들이 겪었던 열 수식 문제를 묻는 내 마지막 게시물에 대한 답장이 없었기 때문에 시간을 할애할 가치가 있는 글을 게시할 시간이나 자료가 없다고 생각했습니다.
지금은 시간이 조금 더 남아서 새로운 도전을 할 때입니다. 다른 시간에 열 공식 문제를 표로 만들고 새로운 도전과 새로운 접근 방식으로 시작하겠습니다. 이 게시물과 아마도 그 이후에 몇 가지에 대해 이야기하겠습니다. 커뮤니티 게시물에 대한 Craige Hales의 응답을 기반으로 하는 일반적인 질문 . 크레이지( @Craige_Hales ), JMP Development에서 은퇴했음에도 불구하고 여기 커뮤니티에서 매우 활발하게 활동하며 사용자 질문에 답변하고 자신의 미지의 블로그 , 이 블로그에 기여합니다. 질문은 루프를 사용하지 않고 (다차원) 목록을 전치하는 효율성에 관한 것이었습니다. 나는 내가 자주 궁금해했던 좀 더 일반적인 질문을 하고 싶습니다. "반복에 대한 더 나은 대안이 있습니까? 그렇다면 대안은 무엇입니까?" 대부분의 경우 더 낫다는 것은 더 빠르다는 것을 의미하지만 속도를 너무 많이 손상시키지 않는 경우 코드 압축도 고려할 것입니다. 또한 차이점이 있는지 확인하기 위해 반복에 대한 다양한 접근 방식을 살펴보겠습니다. 텍스트 검색부터 시작하겠습니다.
문자열
생물정보학의 일반적인 작업은 특정 하위 문자열 패턴을 찾기 위해 유전 정보가 포함된 문자열을 검색하는 것입니다. DNA의 경우 문자열 문자는 A, T, C 및 G의 네 글자로만 구성됩니다. 파일 코로나19.TXT (이 게시물에 첨부)는 약 30,000자 길이의 Covid19 게놈에 대한 유전자 서열을 포함합니다(반면 가장 긴 인간 1번 염색체는 약 2억 9,000만 자). 2-10자 길이의 특정 부분 문자열이 모두 나타나는 위치를 찾기 위해 얼마나 빨리 검색할 수 있습니까?
4가지 접근 방식을 살펴보겠습니다. 그 중 3가지가 반복적입니다. 기술에 관계없이 하위 문자열 일치가 겹칠 수 있습니다. 예를 들어, 밥 에 두 번 들어있다. 바밥 , 위치 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에 있습니다.
| 부분 문자열 길이 |
하위 문자열 |
색인 |
포함 |
팻매치 |
| 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-19배 빠릅니다. 같지 않은 하위 문자열 그러나 검색 시간은 부분 문자열 길이의 함수로 증가합니다.
최종 반복 접근 방식은 다음을 사용합니다. 포함 . 아이디어는 주어진 하위 문자열을 찾고, 검색된 문자열에서 해당 위치를 표시하고, 하위 문자열을 찾을 수 없을 때까지 위치를 지나서 한 문자부터 시작하는 프로세스를 반복하는 것입니다. 이 방법의 매력은 검색된 문자열에 하위 문자열이 거의 없을 때 검색이 매우 빨라진다는 것입니다. 아래 코드는 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;
);
보시다시피, 이 접근 방식은 2자 하위 문자열에 대한 인덱싱 방법보다 약간 느리게 시작하지만 하위 문자열이 길어질수록, 즉 찾을 하위 문자열이 적기 때문에 빠르게 빨라집니다.
마지막 접근 방식은 내가 가장 좋아하는 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개). 125개의 실행은 반올림된 분수 문자열 길이 값을 사용하여 Fast Flexible 설계를 사용하여 생성되었습니다. 각 실행에 대해 임의의 알파벳 문자열이 생성되었습니다. 해당 문자열 내에서 무작위로 생성된 숫자로 구성된 하위 문자열이 임의의 위치에 삽입되었습니다. 빈도 값은 정수가 아닌 삽입 수로 이어질 수 있기 때문에 삽입 횟수는 빈도의 상한선에 검색된 문자열 길이를 1,000으로 나눈 값으로 계산했습니다. 동일한 검색 문자열/하위 문자열 조합에 대해 각 실행을 10회 반복했습니다. 실행을 생성하는 데 사용되는 코드는 다음과 같습니다. 디자인 스크립트 실행.JSL 그리고 결과는 공간 채우기 결과 1.JMP 이 게시물에 첨부합니다.
결과를 빠르게 검사하면 13개의 관찰만 표시됩니다. 포함 메서드가 패턴 일치보다 성능이 좋습니다. 이 중 가장 큰 차이는 약 4,000마이크로초 더 빠릅니다(반면 패턴 일치는 포함 ). Gaussian Process 모델을 데이터에 피팅하면 검색된 문자열 길이 상호 작용에 의해 검색된 문자열 길이가 강한 빈도로 가장 큰 영향을 받음을 시사합니다. 부분 문자열 길이는 거의 영향을 미치지 않았습니다. 선형 모델은 처음에 데이터에 적합했지만 잔차 분석은 적합이 의심스러울 수 있음을 시사했습니다. 나는 게시했다 이에 대한 프로파일러 및 후속 모델의 대화형 버전 JMP 퍼블릭으로.
두 번째 공간 채우기 디자인은 다음과 같은 경우를 더 잘 표현하기 위해 만들어졌습니다. 포함 패턴 일치를 능가했습니다. 이 실험의 경우 두 문자열 길이의 범위는 이전과 동일하게 유지되었으며 빈도는 0과 1 사이에서 변경되었습니다. 결과는 공간 채우기 결과 2.JMP . 결과의 방향은 더 긴 검색 문자열 길이와 패턴 일치를 선호하는 더 높은 빈도로 이전과 유사했습니다.
두 결과 세트를 결합하고 가우스 프로세스 모델을 피팅하면 50,000자 문자열의 경우, 포함 주파수가 2 미만인 경우 더 우수합니다. 100,000자에서 빈도는 1로 떨어지고 200,000자에서 0.5 미만입니다. 이것의 결론은 더 희소한 더 짧은 문자열의 경우 다음을 사용한다는 것입니다. 포함 스트링 길이와 밀도가 증가함에 따라 패턴 매칭이 더 우수할 것입니다.
이달의 도전
Covid19 게놈을 사용하여 두 번 이상 나타나는 가장 긴 부분 문자열을 찾습니다.
이건 다음 포스팅까지 미루지 말고 의논하고 공유합시다. 나는 이것이 매우 어려운 문제라고 생각하며 우리는 공개 토론을 통해 이익을 얻을 것입니다.
상황에 따라 더 나을 수도 있고 좋지 않을 수도 있는 다른 접근 방식을 찾으십시오(확인할 시간이 없었음).
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 );
포함 접근 방식은 아래와 같이 더 간결하게 작성할 수 있습니다. 비교가 제거됨에 따라 이것은 또한 기본 문자열 내에 하위 문자열이 존재하지 않을 때 가장 눈에 띄게 조금 더 빠르게 실행되는 이점이 있습니다.
findSequence = Function({txt, sub},{pos=0,ans={}},
while(pos = contains(txt, sub, pos), insertinto(ans, pos++));
ans;
);
