거대한 문자 시퀀스의 문자 집합 색인 찾기

Question

A-D의 문자 시퀀스가 ​​매우 커서 정확히 40 억이라고 가정 해 봅시다. 내 목표는 문자의 큰 순서 내에서 길이가 30으로 설정된 문자의 여러 새로운 시퀀스의 색인을 찾는 것입니다. 찾고있는 시퀀스에 작은 오류가있는 경우 (문자가 잘못됨) 문제가 증가합니다. 이 문제를 어떻게 해결해야합니까?

간단한 방법은 40 억 개의 텍스트 파일 전체에서 한 번에 한 글자 씩 반복하는 것이지만 메모리가 부족하여 영원히 걸릴 것입니다.

해시 맵을 활용하라는 안내를 받았지만 키 값 쌍으로 사용할 항목을 정확히 모르겠습니다. 정규 표현식을 사용하는 아이디어도 나오지 만, 문제가 해결 될지 확실하지 않습니다. 방향의 측면에서 도움을 주시면 감사하겠습니다. 감사!

Answer 1

이것은 고전적인 문제가 longest common subsequence (LCS) 전화 :

는 여기에 내가 부탁 해요 무엇의 그림입니다. 이를 해결하는 알고리즘이 많이 있습니다. 게놈 프로젝트는 이런 종류의 검색을 많이합니다. 제공된 위키 링크에는 많은 예제가 있습니다. 오류 임계 값은 특별한 경우입니다.

유전자 시퀀싱으로 무엇을하고 있습니까? 나는 단지 4 개의 변수 만 언급하기 때문에 묻습니다.

Answer 2

문자로 인코딩하면 사용하는 2 개마다 14 비트가 낭비됩니다. 단 한 바이트만으로 4 개의 뉴클레오타이드 문자를 인코딩 할 수 있습니다. 그런 다음 절반의 기가 바이트 만 필요합니다. 알고리즘에 관해서는 java.lang.String.indexOf의 코드와 위키 피 디아 페이지의 코드를 Boyer-Moore algorithm에서 연구 할 수 있습니다.

현재 Lucene 색인을 사용했다면 즉시 검색 할 수 있습니다. 이 아이디어는 Lucene에서 30 자마다 하위 시퀀스를 별도의 문서로 인덱싱하는 것입니다. 오류 허용 오차에 관해서는 N 그램을 사용하거나 퍼지 검색을해야합니다 (Lucene 4에서는 편집 거리가 최대 2 또는 3 인 문자열을 빠르게 찾을 수있는 새로운 알고리즘이 있음).

Answer 3

다음은 표현을 처리하기위한 빠르고 쉬운 코드입니다.

public static enum Nucleotide { 
    A,B,C,D; 
} 

public static int setbit(int val, int pos, boolean on) { 
    if (on) { 
        // set bit 
     return val | (1 << (8-pos-1)); 
    } 
    else { 
        // unset bit 
     return val & ~(1 << (8-pos-1));   
    } 
} 

public static int set2bits(int val, int pos, int bits) { 
      // set/unset the first bit 
    val = setbit(val, pos, (bits & 2) > 0); 
      // set/unset the second bit 
    val = setbit(val, pos+1, (bits & 1) > 0); 

    return val; 
} 

public static int setNucleotide(int sequence, int pos, Nucleotide tide) { 
      // set both bits based on the ordinal position in the enum 
    return set2bits(sequence, pos*2, tide.ordinal()); 
} 

public static void setNucleotide(int [] sequence, int pos, Nucleotide tide) { 
      // figure out which element in the array to work with 
    int intpos = pos/4; 
      // figure out which of the 4 bit pairs to work with. 
    int bitpos = pos%4; 
    sequence[intpos] = setNucleotide(sequence[intpos], bitpos, tide);  
} 

public static Nucleotide getNucleotide(int [] sequence, int pos) { 
    int intpos = pos/4; 
    int bitpos = pos%4; 
    int val = sequence[intpos]; 
      // get the bits for the requested on, and shift them 
      // down into the least significant bits so we can 
      // convert batch to the enum. 
    int shift = (8-(bitpos+1)*2);  
    int tide = (val & (3 << shift)) >> shift; 
    return Nucleotide.values()[tide]; 

} 

public static void main(String args[]) { 
    int sequence[] = new int[4]; 
    setNucleotide(sequence, 4, Nucleotide.C); 
    System.out.println(getNucleotide(sequence, 4)); 
} 

분명히 비트 쉬핑이 많이 있지만 분명히 작은 댓글은 무슨 일이 벌어지는 지 이해해야합니다.

물론이 표현의 단점은 4 그룹으로 작업한다는 것입니다. 10 개 뉴클레오티드를 말하고 싶다면 다른 변수를 카운트 어딘가에 두어야합니다. 그러면 마지막 2 개 뉴클레오티드를 알 수 있습니다. 시퀀스는 유용하지 않습니다.

퍼지 매칭은 다른 어떤 것도하지 않으면 무차별 대입으로 수행 될 수 있습니다. 다음에 N 개의 뉴클레오타이드 서열을 취한 다음, 0에서 시작하여 뉴클레오티드 0 : N-1을 확인하고 일치하는 수를 확인하십시오. 그런 다음 1 : N 다음 2 : N + 1 등으로 이동하십시오.