学院：基信学院 学号：2012310360 姓名：余思豪
给定一个DNA序列，这个系列只含有4个字母ATCG，如 S =“CTGTACTGTAT”。给定一个整数值k，从S的第一个位置开始，取一连续k个字母的短串，称之为k-mer（如k= 5，则此短串为CTGTA），然后从S的第二个位置，取另一k-mer（如k= 5，则此短串为TGTAC），这样直至S的末端，就得一个集合，包含全部k-mer 。 如对序列S来说，所有5-mer为 ｛CTGTA，TGTAC，GTACT，TACTG，ACTGT，TGTAT｝
通常这些k-mer需一种数据索引方法，可被后面的操作快速访问。例如，对5-mer来说，当查询CTGTA，通过这种数据索引方法，可返回其在DNA序列S中的位置为｛1，6｝。 问题
现在以文件形式给定 100万个 DNA序列，序列编号为1-1000000，每个基因序列长度为100 。
（1）要求对给定k， 给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部k值。
（2）要求索引一旦建立，查询速度尽量快，所用内存尽量小。 （3）给出建立索引所用的计算复杂度，和空间复杂度分析。 （4）给出使用索引查询的计算复杂度，和空间复杂度分析。
（5）假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应数据查询效率。
（6）按重要性由高到低排列，将依据以下几点，来评价索引方法性能
索引查询速度 索引内存使用
8G内存下，所能支持的k值范围 建立索引时间
摘要：基于数据结构中的哈希算法（2）（6），“倒排索引”法（1）（2）及BDKRHash算法（2）, 建立相应的数学模型，给出分析和结果，对DNA 序列的k-mer index问题给出解决方案。
对于不同的k值建立不同的算法来进行索引来对应当k值较小时，利用基因序列其碱基种类较少（只含A,T,G,C）的特点，由哈希算法进行分析可以想到，将k-mer 看成一个四进制的序列数将其转化为十进制数作为哈希表的关键字（2），并采用倒排索引的方法对哈希表关键字分类整理，建立相应的地址存储单元，实现索引；当k值较大时，考虑到内存溢出的问题（6），采用“BKDRHash算法”对k-mer进行十进制转化，并结合“倒排索引”法（2）建立索引，从而对给定的 k-mer片段进行精确查找，最终输出碱基片段所在位置。
此方案将“哈希(Hash)算法”、“BKDRHash算法”和“倒排索引法”相结合，对哈希算法结构进行优化，提升了运算效率，操作简洁、高效。实现了在基因数据库（3）（4）中对给定的碱基片段的位置进行查找的目的。
关键词：倒排索引，哈希算法，BKDRHash算法，碱基序列，基因数据库 一：符号说明及假设
符号说明
1. sumFile: 把记录分成sumFile个文件存放 sumK-mer1: K-mer的总个数
2. sumK-mer2: K-mer可能出现的不重复的个数 。 3. maxY: 每个文件的最大行数。 4. maxX： 平均每行字符数。 5. fileName:文件名。
6. fileNumber;文件编号,范围是0 - sumFile-1。
7. hashKey1:将K_mer转化后的哈希关键字，是一个十进制整数 。 8. position:记录K-mer所在的DNA序列及在每个序列中的位置 。 9. HZJS:文件里平均每行的字符数。 10. &&：表示连接，如A && B即表示AB。
假设在题目给出的数据中，利用BKDRHash算法转化后不会出现相同的哈希值。
二：问题分析
由文件可知有100万个DNA序列，每个基因序列长度为100，给定一个固定的 k 值，则每行序列有100k1个k-mer，k-mer总数有1000000100k1个。数据量级达到百万至千万，故采用建立哈希表的方法实现索引。
碱基序列由A、T、C、G四种碱基无序组合，当给定K值后，理论有 4k 种k-mer。
比较1000000100k1（实际值）和4k（理论值）的大小：
当K小于等于13时，1000000100k14k，k-mer值会出现重复，K越接近1，重复的越多；
当K大于13时，理论上不会出现重复值。 三，模型建立与算法分析 1. 模型的建立
当K小于等于13时，1000000100k14k，k-mer值会出现重复，k越接近1，重复的越多；此时k较小，以“哈希算法”和“倒排索引”相结合的方法建立索引。 因为k-mer由四种碱基构成，根据进制转换思想（1），将K-mer化为四进制再换算为十进制作为哈希表的关键字。
A-0 T-1 G-2 C-3
从而这四个碱基可以看成一个四进制的序列数，分别将 A,T,G,C赋值 0，1，2，3，可以根据四进制对十进制的转化方法（四进制化为十进制的方法为：假设取定一个序列 TCAGC，则以四进制13023表示，化为十进制:
144343042241340468可以得到用十进制数表示的碱基序列（即468
可以表示序列 TCAGC，为一个哈希关键字）。 采用倒排索引的方法对碱基序列进行分类整理：由于碱基序列号的最大值为1000000101K，将整数以字符形式保存，最大占用7个字符，每行的K-mer序列最大值为101-K,最大占用3个字符，即每个记录最大占位11个字符，假定一个字符占用一个字节，则索引记录共计大小为1000000101K111个字节，即11101KM的字节大小。考虑索引记录保存在一个文件中，会导致
文件太大，不利于索引操作，故将记录保存到1000个文件中。
将哈希关键字除1000取余，余数有0,1,2...999,共1000种，将余数作为文件编号fileNumber,文件名用fileNumber &&„.tet‟来表示；商作为记录在每个文件里面的唯一编号即行号Y，同时采用哈希表记录属性的位置，因此在保存记录时将不记录属性值，属性记录采用“碱基序列号 && 每行的K-mer序列”的格式记录K_mer的位置；将记录保存在文件中。 当K_mer出现重复时，按其出现的先后顺序依次放在同一行。 另外，当k<5时，4<1000，此时将记录保存到4个文件中，较节约内存，其它过程同上。
当K值比较大时，如K取100，根据此种方法算出的哈希值，计算机将无法表示，内存溢出,这种情况参考下述方法：当K大于13时，此时1000000101K4则实际上k出现的K-mer个数少于理论上可能出现的k-mer个数，理论上k-mer序列不会出现重复，但考虑随机事件及内存溢出的问题，采用BKDRHash算法，计算k-mer的哈希值，作为哈希关键字。用“碱基序列号 && 每行的K-mer序列 && k-mer”的格式记录位置信息，其它过程同上。 2. 索引 输入K_mer按前面的方法转化为不同的十进制整数，按照上面的方法即可确定对应的存储位置，到相应文件直接读出那一行数据即可；但当k的取值大于13，需对取出的数据进行筛选，选出正确的k-mer位置。 3. 流程图 开始 输入k值，建立索引 输入k-mer，检索 N 是否存在 Y 输出位置 输出，“无该k-mer值” 结束 4，建立索引流程图
Y 5. 分析
开始 开始 输入k值 初始化文件，内存上限 按行读取文件，将每行的k-mer取出后放入内存 N 判断是否到达内存上限 将数据写入文件并清除内存 文件读取完毕，将最后一份数据写入文件 索引创建完成 复杂度分析（1）（6）问索引的时间复杂为：On
索引时， 需要将待查序列的十进制数值与所有的 k-mer 的十进制数进行比较， 所 以时间复杂度为：On；
查询效率及支持的最大K值 支持100位的K-mer；该模型在建立索引上方法不同， K大于13时，需要筛选重复值，效率比K<13低；
索引查询速度K<13时，1秒内可以出结果；K>13时，时间稍长，2到3秒内可以出结果 ；
索引内存使用（2）索引时只需要一个两个 int 型变量，内存消耗几乎可以不计 3.3.5 G内存下，所能支持的k值范围 1-100。 6. 建立索引时间
因为要将文件的所有数据读一次，同时将K-mer值进行转化，在达到内存上限后还需将数据写入文件，故数据量越大时间消耗越多。
使用软件sublime3.0 当K大于13时
header(\"Content-Type:text/html;charset=utf8\");
ini_set(\"memory_limit\试验设置为1G报错 set_time_limit(0); $DNAObj = new DNA(8); //echo $DNAObj->strToHash('ATGC');
//$DNAObj->run();//create index建立索引 $DNAObj->indexK_low('AAGGCAAA');//index class DNA { private $K; private $sumFile; private $arrfileNumber;
private $HZJS;//平均每行的最大字符数 private $startRAM; private $nowRAM; private $romLimit; function __destruct() { }
function DNA($K) {
$this->startRAM = memory_get_usage();//获取初始内存占用情况 //echo $this->startRAM.'
'; $this->K = $K;
switch ($this->K %5) { case 0:
$this->sumFile = pow(4,$this->K); break; default: $this->sumFile = 1000; break; }
$this->romLimit = 1024*1;//测试时设置为１Ｍ $this->HZJS= 100000;// } function run() {
for ($i=0; $i < $this->sumFile; $i++) { $this->arrfileNumber[$i] = 10; } echo \"开始\"; $this->initFile();
if ($this->K<14 & $this->K >0) { $this->K_low(); } elseif($this->K<101){ $this->K_high(); } else{
echo \"输入出错\"; } } function K_low()
{//Ｋ值取指较小时建立索引 $num = 1; $isWrite = 1;
$resFile = fopen(\"/var/www/html/01.fa\(!feof($resFile)) { if ($num == 1) {
$num = 2;
$DNAstr = fgets($resFile, 150); }else{ $DNAstr = fgets($resFile, 150); for($i=1;$i<=(101-$this->K);$i++) { $k_mer = substr($DNAstr, $i,$this->K); $hashKey1 = $this->strToHash($k_mer); $fileNumber = $hashKey1%$this->sumFile; $Y = floor($hashKey1/$this->sumFile);
if ($Y >$this->arrfileNumber[$fileNumber])
{ $this->fileAdd($fileNumber,$Y-$this->arrfileNumber[$fileNumber]);
$this->arrfileNumber[$fileNumber] = $Y; } $position = ' '.$hang.','.$i;
if (isset($arrJL[$fileNumber][$Y])) { $arrJL[$fileNumber][$Y] = $arrJL[$fileNumber][$Y].$position; }else{ $arrJL[$fileNumber][$Y] = $position; }
$this->nowRAM = memory_get_usage();//获取当前内存占用情况 $ram = ($this->nowRAM - $this->startRAM )/10224/2;//ＫＢ if($ram > $this->romLimit)//试验时设为1Ｍ { for ($i=0; $i < $this->sumFile; $i++) { $fileName = '/var/www/html/DNAfile/'.$i.'.txt'; $NewFile = fopen($fileName,'r'); $j = 0; while (!feof($NewFile)) {
if (isset($arrJL[$i][$j])) { $arrLS[$j] = fgets($NewFile, $this->HZJS).$arrJL[$i][$j]; unset($arrJL[$i][$j]); }else{
$arrLS[$j] = fgets($NewFile, $this->HZJS); } $j++; }
fclose($NewFile);
file_put_contents($fileName,\"\"); $NewFile = fopen($fileName,'w');
foreach ($arrLS as $key => $value) { fputs($NewFile,$value); unset($value); } fclose($NewFile);
} } } $hang++; $num = 1; } } } echo \"2
\"; fclose($resFile);
$resFile = fopen(\"/var/www/html/02.fa\fclose($resFile);
echo \"建立索引完成
\"; } function K_high()
{//Ｋ值取指较大时建立索引 $num = 1;
$resFile = fopen(\"/var/www/html/01.fa\(!feof($resFile)) { if ($num == 1) {
$num = 2;
$DNAstr = fgets($resFile, 150); }else{
$DNAstr = fgets($resFile, 150); for($i=1;$i<=(101-$this->K);$i++) {
$k_mer = substr($DNAstr, $i,$this->K); $hashKey1 = $this->MYHash($k_mer); $fileNumber = $hashKey1%$this->sumFile; $Y = floor($hashKey1/$this->sumFile); if ($Y >$this->arrfileNumber[$fileNumber]) {
$this->fileAdd($fileNumber,$Y-$this->arrfileNumber[$fileNumber]); $this->arrfileNumber[$fileNumber] = $Y; } $position = ' '.$hang.','.$i;
if (isset($arrJL[$fileNumber][$Y])) { $arrJL[$fileNumber][$Y] = $arrJL[$fileNumber][$Y].$position.$k_mer; }else{ $arrJL[$fileNumber][$Y] = $position; }
$this->nowRAM = memory_get_usage();//获取当前内存占用情况 $ram = ($this->nowRAM - $this->startRAM )/10224/2;//ＫＢ if($ram > $this->romLimit) {
for ($i=0; $i < $this->sumFile; $i++) { $fileName = '/var/www/html/DNAfile/'.$i.'.txt'; $NewFile = fopen($fileName,'r'); $j = 0; while (!feof($NewFile)) {
$tmpstr2 = fgets($NewFile, $this->HZJS); if (isset($arrJL[$i][$j])) { $arrLS[$j] = $tmpstr2.$arrJL[$i][$j]; unset($arrJL[$i][$j]); }else{ $arrLS[$j] = $tmpstr2; } $j++; }
fclose($NewFile);
$NewFile = fopen($fileName,'w'); for ($j=0; $j < $this->sumFile; $j++) {
if (isset($arrLS[$j])) {
fputs($NewFile,$arrLS[$j]); unset($arrLS[$j]); }else{ } } fclose($NewFile); } } } $hang++; $num = 1; } } }
fclose($resFile);
$resFile = fopen(\"/var/www/html/02.fa\fclose($resFile);
echo \"建立索引完成
\"; }
function strToHash($K_mer) { $hash = 0;
$len = strlen($K_mer);
for ($i=0; $i < $len; $i++) { $ch = substr($K_mer,$i,1); switch ($ch) { case 'A': $hash = $hash+0*pow(4, $len-1-$i); break; case 'T': $hash = $hash+1*pow(4, $len-1-$i); break; case 'G': $hash = $hash+2*pow(4, $len-1-$i); break; case 'C': $hash = $hash+3*pow(4, $len-1-$i); break; default: break; } } return $hash; }
function MYHash($str) {//BKDRHash哈希算法
$seed = 131; // 31 131 1313 13131 131313 etc.. $hash = 0; $cnt = strlen($str); for($i = 0; $i < $cnt; $i++) {
$hash = ((floatval($hash * $seed) & 0x7FFFFFFF) + ord($str[$i])) & 0x7FFFFFFF;
return floor(($hash & 0x7FFFFFFF)%100000019);//将原算法改进以下，降低ｈａｓｈ值的大小 } function initFile() {
for ($i=0; $i < $this->sumFile; $i++) {
$fileName = '/var/www/html/DNAfile/'.$i.'.txt'; $NewFile = fopen($fileName,'w'); //初始化文件每行先预留１０行 for ($j=0; $j < 10-1; $j++) { //fputs($NewFile,$j); fputs($NewFile,\"\\n\"); }
fclose($NewFile); } }
function fileAdd($fileNumber,$add) {//在运行中增加行数
$fileName = '/var/www/html/DNAfile/'.$fileNumber.'.txt'; $NewFile = fopen($fileName,'a'); for ($j=0; $j < $add; $j++) { //fputs($NewFile,$j); fputs($NewFile,\"\\n\"); }
fclose($NewFile); } function indexK_low($str) {
$hashKey1 = $this->strToHash($str);
$fileNumber = $hashKey1%$this->sumFile; $Y = floor($hashKey1/$this->sumFile);
$fileName = '/var/www/html/DNAfile/'.$fileNumber.'.txt'; $NewFile = fopen($fileName,'r'); $j = 0; echo $str; echo \"
\";
while (!feof($NewFile)) {
$position = fgets($NewFile, $this->HZJS); if ($j==$Y) { echo $position.''; } $j++;
fclose($NewFile); } function indexK_high($str) { $hashKey1 = $this->MYHash($str);
$fileNumber = $hashKey1%$this->sumFile; $Y = floor($hashKey1/$this->sumFile); $fileName = '/var/www/html/DNAfile/'.$fileNumber.'.txt'; echo $str; echo \"
\"; $NewFile = fopen($fileName,'r'); for ($j=0; $j <= $Y; $j++) { $position = fgets($NewFile, $this->HZJS); } fclose($NewFile); $len = strlen($str);
preg_match_all(\"/[^\\s ]+/s\这里除了匹配 空格，还匹配中文全角的空格 \\s后面直接加上就是了 $arr = $arr[0];
if ( count($arr) == 1) { echo $arr[0]; exit(); } foreach ($arr as $key => $value) {
if (strlen($value) > 20) {//判断为含有Ｋ-mer信息
$str2 = substr($value, strlen($value) - $len, $len); if(strcmp($str, $str2) == 0) { echo $str2; echo \"
\"; } }else{ echo $arr[0]; } } } } ?> 19
哈希算法：
class GeneralHashFunctionLibrary{
public long RSHash(String str) {
int b = 378551; int a = 63689; long hash = 0;
for(int i = 0; i < str.length(); i++) {
hash = hash * a + str.charAt(i); a = a * b; }
return hash; }
public long JSHash(String str) {
long hash = 1315423911; for(int i = 0; i < str.length(); i++) {
hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2)); }
return hash; }
public long PJWHash(String str) {
long BitsInUnsignedInt = (long)(4 * 8);
long ThreeQuarters = (long)((BitsInUnsignedInt * 3) / 4); long OneEighth = (long)(BitsInUnsignedInt / 8);
long HighBits = (long)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); long hash = 0; long test = 0;
for(int i = 0; i < str.length(); i++) {
hash = (hash << OneEighth) + str.charAt(i); if((test = hash & HighBits) != 0) {
hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits)); } }
return hash; }
public long ELFHash(String str) {
long hash = 0; long x = 0;
for(int i = 0; i < str.length(); i++) {
hash = (hash << 4) + str.charAt(i); if((x = hash & 0xF0000000L) != 0) {
hash ^= (x >> 24); }
hash &= ~x; }
return hash; }
public long BKDRHash(String str) {
long seed = 131; // 31 131 1313 13131 131313 etc.. long hash = 0;
for(int i = 0; i < str.length(); i++) {
hash = (hash * seed) + str.charAt(i); }
return hash; }
public long SDBMHash(String str) {
long hash = 0;
for(int i = 0; i < str.length(); i++) {
hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash; }
return hash; }
public long DJBHash(String str) {
long hash = 5381;
for(int i = 0; i < str.length(); i++) {
hash = ((hash << 5) + hash) + str.charAt(i); }
return hash; }
public long DEKHash(String str) {
long hash = str.length(); for(int i = 0; i < str.length(); i++) {
hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i); }
return hash; }
public long BPHash(String str) {
long hash = 0;
for(int i = 0; i < str.length(); i++) {
hash = hash << 7 ^ str.charAt(i); }
return hash; }
public long FNVHash(String str) {
long fnv_prime = 0x811C9DC5; long hash = 0;
for(int i = 0; i < str.length(); i++) {
hash *= fnv_prime; hash ^= str.charAt(i); }
return hash; }
public long APHash(String str) {
long hash = 0xAAAAAAAA; for(int i = 0; i < str.length(); i++) {
if ((i & 1) == 0) {
hash ^= ((hash << 7) ^ str.charAt(i) ^ (hash >> 3)); } else {
hash ^= (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5))); } }
return hash; } }
倒排索引法： 简单法折叠
索引的构建相当于从正排表到倒排表的建立过程。当我们分析完网页时 ,得到的是以网页为主码的索引表。当索引建立完成后 ,应得到倒排表 ,具体流程如图所示: 流程描述如下:
1)将文档分析称单词term标记， 2)使用hash去重单词term 3)对单词生成倒排列表
倒排列表就是文档编号DocID，没有包含其他的信息(如词频，单词位置等)，这就是简单的索引。
这个简单索引功能可以用于小数据，例如索引几千个文档。然而它有两点限制:
1)需要有足够的内存来存储倒排表，对于搜索引擎来说， 都是G级别数据，特别是当规模不断扩大时 ,我们根本不可能提供这么多的内存。 2)算法是顺序执行，不便于并行处理。 合并法折叠 归并法,即每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。
归并法,即每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。
归并索引如图 归并示意图:
合并流程:
1)页面分析，生成临时倒排数据索引A，B，当临时倒排数据索引A，B占满内存后，将内存索引A，B写入临时文件生成临时倒排文件，
2) 对生成的多个临时倒排文件 ,执行多路归并 ,输出得到最终的倒排文件 ( inverted file)。
合并流程索引创建过程中的页面分析 ,特别是中文分词为
主要时间开销。算法的第二步相对很快。这样创建算法的优化集中在中文分词效率上。
因篇幅问题不能全部显示，请点此查看更多更全内容