시퀀스를 비트 단위로 인코딩하여 메모리 요구 사항을 확실히 제거 할 수 있습니다. 16 개의 상태 또는 4 비트 인 “ACGT”를 사용하여 길이 2에 대한 순열을보고 있습니다. 길이 3의 경우 64 개 상태이며 6 비트로 인코딩 할 수 있습니다. 따라서 시퀀스의 각 문자에 대해 2 비트 또는 16 문자에 대해 약 32 비트처럼 보입니다.

유효한 ‘단어’의 수를 줄이는 방법이 있다면 추가 압축이 가능할 수 있습니다.

따라서 길이가 3 인 시퀀스의 경우 크기가 uint32 또는 uint64 인 64 개의 버킷을 만들 수 있습니다. 그것들을 0으로 초기화하십시오. 매우 큰 3 개의 문자 시퀀스 목록을 반복하고 위와 같이 인코딩하십시오. 이것을 첨자로 사용하고 해당 버킷을 늘리십시오.
모든 시퀀스가 ​​처리 될 때까지이 과정을 반복하십시오.

다음으로 목록을 재생성하십시오.

64 개의 버킷을 순서대로 반복하여 해당 버킷에서 발견 된 수에 대해 해당 버킷으로 표시되는 시퀀스의 많은 인스턴스를 생성합니다.
모든 버킷이 반복되면 정렬 된 배열이 있습니다.

4의 시퀀스는 2 비트를 추가하므로 256 개의 버킷이 있습니다. 5의 시퀀스는 2 비트를 추가하므로 1024 개의 버킷이 있습니다.

어느 시점에서 버킷 수가 한계에 도달합니다. 파일에서 시퀀스를 메모리에 보관하지 않고 읽는 경우 버킷에 더 많은 메모리를 사용할 수 있습니다.

버킷이 작업 세트에 맞을 가능성이 있기 때문에 현장에서 정렬하는 것보다 이것이 더 빠를 것이라고 생각합니다.

기술을 보여주는 해킹입니다.

#include <iostream>
#include <iomanip>

#include <math.h>

using namespace std;

const int width = 3;
const int bucketCount = exp(width * log(4)) + 1;
      int *bucket = NULL;

const char charMap[4] = {'A', 'C', 'G', 'T'};

void setup
(
    void
)
{
    bucket = new int[bucketCount];
    memset(bucket, '\0', bucketCount * sizeof(bucket[0]));
}

void teardown
(
    void
)
{
    delete[] bucket;
}

void show
(
    int encoded
)
{
    int z;
    int y;
    int j;
    for (z = width - 1; z >= 0; z--)
    {
        int n = 1;
        for (y = 0; y < z; y++)
            n *= 4;

        j = encoded % n;
        encoded -= j;
        encoded /= n;
        cout << charMap[encoded];
        encoded = j;
    }

    cout << endl;
}

int main(void)
{
    // Sort this sequence
    const char *testSequence = "CAGCCCAAAGGGTTTAGACTTGGTGCGCAGCAGTTAAGATTGTTT";

    size_t testSequenceLength = strlen(testSequence);

    setup();


    // load the sequences into the buckets
    size_t z;
    for (z = 0; z < testSequenceLength; z += width)
    {
        int encoding = 0;

        size_t y;
        for (y = 0; y < width; y++)
        {
            encoding *= 4;

            switch (*(testSequence + z + y))
            {
                case 'A' : encoding += 0; break;
                case 'C' : encoding += 1; break;
                case 'G' : encoding += 2; break;
                case 'T' : encoding += 3; break;
                default  : abort();
            };
        }

        bucket[encoding]++;
    }

    /* show the sorted sequences */
    for (z = 0; z < bucketCount; z++)
    {
        while (bucket[z] > 0)
        {
            show(z);
            bucket[z]--;
        }
    }

    teardown();

    return 0;
}

답변

sort(List<string> elements, int prefix)
    if (elements.Count < THRESHOLD)
         return InMemoryRadixSort(elements, prefix)
    else
         return DiskBackedRadixSort(elements, prefix)

DiskBackedRadixSort(elements, prefix)
    DiskBackedBuffer<string>[] buckets
    foreach (element in elements)
        buckets[element.MSB(prefix)].Add(element);

    List<string> ret
    foreach (bucket in buckets)
        ret.Add(sort(bucket, prefix + 1))

    return ret

GATTACA