查找最常見的k聚體和它們在C++

Question

外觀的數量對於k聚https://en.wikipedia.org/wiki/K-mer

我試圖找到一個大的fastq文件最常見的k聚體。我的計劃是使用MISRA-格里斯算法來找出最頻繁的k聚體，然後用第二遍搜索每一個頻繁k鏈節的數量在文件中。但我認爲我的算法不夠高效。以下是我的第一份草案。我儘量內存儘可能高效。（程序不能運行內存不足）

我也發現了這個DSK算法，但是這個人是太難受，沒有看到一個簡單的實現理解。 http://minia.genouest.org/dsk/

注：另外每個櫃檯的ID將是整數不是字符串，我要在我的最後草案進行更改。

#include <iostream> 
#include <fstream> 
#include <sstream> 
#include <vector> 
using namespace std; 

struct node { 
    string id; 
    int count; 
}; 

void searchCount(vector <node>&memory, string line,int k) { 
    int count = 0; 
    string kMer; 
    for (int i = 0; i < memory.size(); i++) { 
     if (memory[i].id != "") { 
      for (int j = 0; j < line.length() - k + 1; j++) { 
       kMer = line.substr(j, k); 
       if (kMer == memory[i].id) { 
        count++; 
       } 
      } 
     } 
     memory[i].count = count; 
     count = 0; 
    } 
} 

int doWeHaveSpace(vector <node> memory) { 
    for (int i = 0; i < memory.size(); i++) { 
     if (memory[i].id == "") { 
      return i; 
     } 
    } 
    return -1; 


} 

void MisraGries(string element, vector <node> &memory) { 
    bool isHere = false; 
    int index; 

    for (int i = 0; i < memory.size(); i++) { 
     if (memory[i].id == element) { 
      isHere = true; 
      index = i; 
     } 
    } 
    if (isHere) { 
     memory[index].count++; 
    } 
    else { 
     int freeIndex = doWeHaveSpace(memory); 
     if (freeIndex+1) { 
      memory[freeIndex].count++; 
      memory[freeIndex].id = element; 
     } 
     else { 
      for (int i = 0; i < memory.size(); i++) { 
       if (memory[i].count != 0) { 
        memory[i].count--; 
        if (memory[i].count == 0) { 
         memory[i].id = ""; 
        } 
       } 
      } 
     } 
    } 
} 
void filecheck(ifstream & input, string prompt) // this function checks and opens input files 
{ 
    string filename; 
    cout << "Please enter file directory and name for " << prompt << ": "; 
    do 
    { 
     getline(cin, filename); 
     input.open(filename.c_str()); 
     if (input.fail()) 
      cout << " wrong file directory. Please enter real directory. "; 
    } while (input.fail()); 
} 

int main() { 
    int line = 1; 
    string filename; 
    ifstream input; 
    ofstream output; 
    string search; 
    vector <node> frequent(1000); 
    for (int i = 0; i < frequent.size(); i++) { 
     frequent[i].id = ""; 
     frequent[i].count = 0; 
    } 
    int k = 30; 
    string kMer; 
    filecheck(input, "input file"); 

    while (!input.eof()) 
    { 
     getline(input, search); // it gets infos line by line to count lines 
     line++; 
     if (line == 3) { 
      for (int i = 0; i < search.length() - k + 1; i++) { 
       kMer = search.substr(i, k); 
       MisraGries(kMer, frequent); 
      } 
      line = -1; 
     } 

    } 

    return 0; 
} 

Answer 1

您可以通過將最常見的k-mers存儲在散列表而不是數組中來加速代碼。這樣，你就可以處理一個k鏈節在O(1)時間（假設長度爲常數），如果它已經在緩存中（如果它不是，它仍然需要一個直線傳球，但它可能帶來了很大的平均改善）。

如果通過在某種輔助數據結構（如優先級隊列）中保留附加信息導致大量未命中，您可以更快地找到該元素，並且可以在不檢查的情況下刪除它們所有其他元素。

考慮到k在您的示例中非常小，您可以增加內存緩存的大小（典型的計算機應該很容易在內存中保留幾百萬個這樣的字符串），從而減少失誤。

你甚至可以更多的數據通過散列k聚體第一遍時存儲（這樣，你只需要存儲整數在內存中，而不是字符串）。總結一下，我會建議讓緩存更大（只要它適合內存），並使用更適合的數據結構來支持快速查找，如散列表（C++中的std::unordered_map）。