B2-2015年深圳杯优秀论文-DNA序列问题

基于散列表的杫札杭来杲序列快速查找算法 摘要 生物序列的杫札杭来杲频次统计是生物信息处理中一个非常基础且重要的问题朮本文将针对 特定长度的基因序列分析杫札杭来杲的频率分布本尝试使用不同的散列函数建立合适的散列表作 为数据索引本分析算法的时间和空间复杂度本并根据计算机处理数据的特点进行算法优化朮 朱 关键词： 散列函数 k-mer 复杂度 蔡琪 朱鹤 朱问题的重述 给定一个杄李杁序列本这个系列只含有朴个字母杁杔权杇本如 杓 朽朢权杔杇杔杁权杔杇杔杁杔朢朮给定一 个整数值杫本从杓的第一个位置开始本取一连续杫个字母的短串本称之为杫札杭来杲（如杫朽 朵本则此短串 为权杔杇杔杁）本 然后从杓的第二个位置本 取另一杫札杭来杲（如杫朽 朵本则此短串为杔杇杔杁权）本这样直 至杓 的末端本就得一个集合本包含全部杫札杭来杲 朮 如对序列杓 来说本所有朵札杭来杲为权杔杇杔杁本杔杇杔杁权本 杇杔杁权杔本杔杁权杔杇本杁权杔杇杔本杔杇杔杁杔通常这些杫札杭来杲需一种数据索引方法本可被后面的操作 快速访问朮例如本对朵札杭来杲来说本当查询权杔杇杔杁本通过这种数据索引方法本可返回其在杄李杁序列杓中 的位置为朱本朶朮 现在以文件形式给定 朱朰朰万个 杄李杁序列本序列编号为朱札朱朰朰朰朰朰朰本每个基因 序列长度为朱朰朰 朮 朱朮 要求对给定杫本 给出并实现一种数据索引方法本可返回任意一个杫札杭来杲所在的杄李杁序列 编号和相应序列中出现的位置朮每次建立索引本只需支持一个杫值即可本不需要支持全部杫值朮 朲朮 要求索引一旦建立本查询速度尽量快本所用内存尽量小朮 朳朮 给出建立索引所用的计算复杂度本和空间复杂度分析朮 朴朮 给出使用索引查询的计算复杂度本和空间复杂度分析朮 朵朮 假设内存限制为朸杇本分析所设计索引方法所能支持的最大杫值和相应数据查询效率朮 朱朮朱问题分析 对于问题一本朱朰6朱朰朰的杄李杁序列本当杫较小时本对应的杫札杭来杲重复率会很高本为了快速检 索任意一个杫札杭来杲所在的杄李杁序列编号和相应序列中出现的位置本需要去除序列中重复冗余 的信息本建立合适的数据索引朮建立索引的方法大致有两种：基于杨条杳杨的和基于杂杗杔朮 题目 中要求每次建立的索引只需支持一个杫值本且杄李杁序列的总数不是太大本我们采用对序列建 立散列表作为数据索引的方法朮通过建立散列表可以实现杏木朱朩的查找速度本并且可以很容易 的利用多线程编程加快建立索引的速度朮我们将根据分析的序列信息采用合适的参数建立 散列表朮 对于问题二本散列表在没有冲突的情况下可以实现杏（朱）的查找速度本为了提高检索 速度朮我们采用以空间换取时间的策略本在内存限制范围内本设置比较大的散列表本从而减少冲 突的概率朮冲突解决策略的选择也会影响查询的速度本好的冲突解决策略可以减少因冲突产 生的探测次数本提高检索速度朮原序列的保存采用字符型变量本为了节省空间本我们采用二进制 表示四种字符本可以将数据量压缩到朲朵朥朮 对于问题三本分析建立索引的时间、空间复杂度朮对于不同长度的杫札杭来杲本我们分析平 均时间复杂度和最坏情况时间复杂度朮同时根据序列的概率分布情况可以得到更加准确的 时间和空间利用朮 于问题四本通过建立散列表查询的时间和空间复杂度都是常数级的本通过分析序列的 分布情况可以得到更加准确的时间空间分布朮 对于问题五本在允许的朸杇内存限制下本根据杫札杭来杲的长度分析保存地址信息需要的节 点数目本进而得出最大允许的杫札杭来杲长度朮 朲 朲基本假设 朱朮 假设题目所给数据及建模收集数据可以代表一般情形 朲朮 假设采用的散列函数对不同序列生成的散列值不同 朳朮 程序测试都是在杷杩杮朸朮朱末杉杮杴来杬 杣杯杲来 杩朷本朲朮朴杇杈杺末内存朸杇末 杖杩杳杵条杬 杓杴杵杤杩杯 权杯杭杭杵杮杩杴杹 朲朰朱朳 平台上完成 朳模型的建立与求解 朳朮朱问题一机建立数据索引 对基因序列的分析已有研究发现本杄李杁序列中的短序列片段（通常长度为朶 个碱基以下） 不仅具有高度重复性本而且在杄李杁序列中的分布是具有一定特点的朮杔杲杩杦杯杮杯杶和杓杵杳杳杭条杮提出 杄李杁序列中短序列片段的频率分布呈现为一条具有相对稳定性的曲线本后来杂杯杲杯杤杯杶杳杫杹和 杓杰杲杩杺杨杩杴杳杫杩杩 通过实验研究和数据分析验证和支持了这一理论朮杄李杁序列的这一特征是作为 生物学数据所具有的特异性表现本从某种程度上代表和反映了生物的本质特征朮通过对这些 序列分布是否均匀进行分析本可以更好的选择散列表的参数朮 杋杌散度杛朱杝 杋杵杬杬杢条杣杫札杌来杩杢杬来杲杄杩杶来杲杧来杮杣来是统计学家杋杵杬杬杢条杣杫和杌来杩杢杬来杲于朱朹朵朱年提出的一种 相关熵表示方法本能度量两个离散或连续概率分布杰和東 之间的差异或接近程度朮本文通过将 序列的杫札杭来杲频数分布映射成相应的概率分布本来对比分析实际杄李杁序列与等长随机序列之 间杫札杭来杲 分布的差异朮 对于长度为k的杫札杭来杲本不同的杫札杭来杲种类数为朴k本假设每种杫札杭来杲出现的 频数为ni本其中i 朽 朱,朲,.,朴k本则在一条长度为L的杄李杁序列中本杫札杭来杲分布概率表示为pi朽 ni Lk+1本设实际杄李杁序列的杫札杭来杲分布概率表示为pi本杁、杇、权、杔四种碱基等概率均匀分布 的随机序列的杫札杭来杲分布概率表示为qi本则pi本qi的杋杌散度可以由如下公式计算： DKL木p|q朩 朽 4k X i=1 pilog木pi qi 朩木朱朩 由公式木朱朩可以看出本DKL木p|q朩 朽 朰恒成立朮当pi本qi的概率分布完全相同时本杋杌散度值为 零本表示两个序列完全一样朮序列中碱基排列不一致时本杋杌 散度大于零朮试验中假设等长随机 序列之间杫札杭来杲均匀分布本则机 qi朽 朱 朴k i 朽 朱,朲,.,朴k木朲朩 郝柏林院士等在 朲朰朰朰 年提出了一种使用朲杄 分形图像的可视化方法来反映序列的杫札 杭来杲 的频次分布本并在此基础上设计了基于杂 树的快速杫札杭来杲 频次统计算法杛朲杝朮杄李杁序列中 的每一个杫札杭来杲都可以映射成坐标平面上的一个点（杸本杹）本相同的杫札杭来杲对应的（杸本杹）坐标 相同本不同的坐标点对应了不同的杫札杭来杲本某一个坐标点的值越大本表示该点对应的杫札杭来杲在整 个杄李杁序列中出现的频率越高朮对于k 朸时本将序列对应的杸本杹坐标对朲朵朶取余数后绘制的部分图像如下： 图 朴机 杫朽朲朰图 朵机 杫朽朶朰图 朶机 杫朽朱朰朰 根据绘制的图像可以看出来本颜色分布基本均匀本说明不同序列的频数分布大致相同朮在 下面的分析中我们认为对于任意的杫值本不同杫札杭来杲的分布为均匀分布朮 朳朮朱朮朱散列函数的选择 散列函数是一种从任何一种数据中创建小的数字朢指纹朢的方法朮散列函数把消息或数 据压缩成摘要，使得数据量变小，将数据的格式固定下来朮好的散列函数在输入域中很少出 现散列冲突朮利用散列值作为数据保存的位置索引，可以使访问速度达到O木朱朩的时间复杂 度朮 下表杛朳杝是对常用的散列函数的测试本测试数据一是 朲朱朶朵朵朳个英文单词本测试数据二是朲朱朶朵朵朳个随机杇杕杉杄，测试数据三是从朱到朲朱朶朵朵朳的数值朮对 于每组测试数据记录了平均散列时间和冲突数机 朴 表 朲机 散列函数对比 杈条杳杨杌杯杷来杲杣条杳来杒条杮杤杯杭 杕杕杉杄李杵杭杢来杲杳 杍杵杲杭杵杲杈条杳杨朱朴朵 杮杳朲朵朹 杮杳朹朲 杮杳 朶 杣杯杬杬杩杳朵 杣杯杬杬杩杳朰 杣杯杬杬杩杳 杆李杖札朱条朱朵朲 杮杳朵朰朴 杮杳朸朶 杮杳 朴 杣杯杬杬杩杳朴 杣杯杬杬杩杳朰 杣杯杬杬杩杳 杆李杖札朱朱朸朴 杮杳朷朳朰 杮杳朹朲 杮杳 朱 杣杯杬杬杩杳朵 杣杯杬杬杩杳朰 杣杯杬杬杩杳未 杄杂杊朲条朱朵朸 杮杳朴朴朳 杮杳朹朱 杮杳 朵 杣杯杬杬杩杳朶 杣杯杬杬杩杳朰 杣杯杬杬杩杳未未未 杄杊杂朲朱朵朶 杮杳朴朳朷 杮杳朹朳 杮杳 朷 杣杯杬杬杩杳朶 杣杯杬杬杩杳朰 杣杯杬杬杩杳未未未 杓杄杂杍朱朴朸 杮杳朴朸朴 杮杳朹朰 杮杳 朴 杣杯杬杬杩杳朶 杣杯杬杬杩杳朰 杣杯杬杬杩杳 杓杵杰来杲杆条杳杴杈条杳杨朱朶朴 杮杳朳朴朴 杮杳朱朱朸 杮杳 朸朵 杣杯杬杬杩杳朴 杣杯杬杬杩杳朱朸朷朴朲 杣杯杬杬杩杳 权杒权朳朲朲朵朰 杮杳朹朴朶 杮杳朱朳朰 杮杳 朲 杣杯杬杬杩杳朰 杣杯杬杬杩杳朰 杣杯杬杬杩杳 杌杯杳来杌杯杳来朳朳朸 杮杳札札 朲朱朵朱朷朸 杣杯杬杬杩杳札札 散列函数的选择主要考虑计算时间和冲突的数目本综合上面已有的数据本我们采用 杍杵杲杭杵杲杈条杳杨作为散列函数朮杍杵杲杭杵杲杈条杳杨 是一种非加密型哈希函数，适用于一般的哈希检 索操作朮由杁杵杳杴杩杮 杁杰杰杬来杢杹在朲朰朰朸年发明杛朴杝，并出现了多个变种，都已经发布到了公有领 域朮与其它流行的哈希函数相比，对于规律性较强的杫来杹，杍杵杲杭杵杲杈条杳杨的随机分布特征表 现更良好朮对于满足朴k H的杫值本利用表朲的对应关系把序列对应的二进制数作为散列 值本可以节省计算散列值的时间本也完全避免了冲突的产生朮如对于序列朢杁杔权杇朢，其对应的 哈希值为”朰朰朰朱朱朰朱朱杢朢朮 朳朮朱朮朲散列表的大小 散列表的大小必须大于序列种类数才可以保存所有的数据朮设，H表示散列表的大小， Bk表示长度为k的杫札杭来杲的种类数，m表示每条杄李杁序列的长度，n表示杄李杁序列的数目。 散列表的最小值可以由以下公式确定： H 杭条杸 k Bk 朽 杭条杸 k 杭杩杮朴k,木m k 末 朱朩 n k 朽 朱,朲,.,朱朰朰木朳朩 通过计算可以得到当k 朽 朱朴的时候本杋取得最大值本为朸朷朱朰6本这就要求为了确保可以建立杫从朱 到朱朰朰的所有索引本必须要求散列表的大小不小于朸朷朱朰6朮根据对给定的基因序列进行分析本我 们得到Bk与杫的关系曲线如下： 朵 图 朷机 杫朽朲朰 根据测算的数据本当杫朽朱朷是本Bk取得最大值本为朱朹朶朸朲朳朹朹朮设散列表中非空位置的数目 为H1本散列表的载荷因子定义为： 朽H1 H 朮 太大会使冲突的数目增多，降低建立索引和 查询的时间，太小会浪费存储空间，需要根据实际情况调整的大小朮 朳朮朱朮朳散列表节点的选择 每个散列表节点要保存对应杫札杭来杲序列的标识符和地址本我们采用如下图所示的数据结 构 图 朸机 散列节点结构图 朹机 地址节点结构 散列节点中的杈条杳杨 杉杄保存序列生成的散列值的高朶朴位作为识别序列的标志本 杁杤杤杲来杳杳 李杯杤来 杰杴杲为指向地址节点的指针本地址节点保存该序列的地址的指向下一个同一序 列地址节点的指针朮添加一个杫札杭来杲序列SK时本若散列表中对应位置的Hash ID为朰时本将该序 列的Hash ID保存到该节点中本将地址保存到节点的地址空间中；如果散列表对应的位置 Hash ID不为朰本则分配一个新的杁杤杤杲来杳杳 李杯杤来 保存该序列的信息朮最坏情况下本出了第一个 插入的序列外其他的序列全部发送冲突。需要申请新的节点数HN为机 HN朽 木m k 末 朱朩 n 朱木朴朩 朶 使用杘朸朶程序占用的空间大小约为朷朶朲杍杂本使用杸朶朴程序占用的空间约为朱朱朴朳杍杂本经测 试可以申请足够空间朮 散列表的结构如下图所示： 图 朱朰机 散列表结构 朳朮朲合适的冲突解决方法 解决冲突的方法主要有开放寻址法和链接技术朮由于在散列表中需要保存序列的地址本每 个节点后面连接了一个链表本故采用开放寻址法解决冲突。开放寻址法主要有：线性探查本二 次探查本再散列本双重散列朮线性探查计算下一个节点速度较快本但是可能出现堆积导致探 测次数过多朮二次探查可能出现再次求出的地址经过几次过程后回到起始地址本从而进入死 循环朮再散列的方法可以避免线性探查导致的堆积现象本但当散列表中的空位较少时可能很 难找到空位朮 我们通过散列函数产生的散列值对散列长度取模作为该序列在散列表中的地 址朮对于不同的杫值我们测得在散列表的长度杈朽朴朹朹朹朹朹朹朱大小下冲突的次数本测量数据如下 所示： 朷 图 朱朱机 线性探查的冲突数 与杫的关系 图 朱朲机 一次再散列末 线性 探查冲突数与 杫 的关系 图 朱朳机 二次再散列末 线性 探查冲突数与 杫 的关系 朳朮朲朮朱充分利用计算机的性能 预先将序列读取到内存中计算机从内存和磁盘中读取的速度差别在两个数量级左右本为 了提高运行时的速度本减少计算机多次从磁盘中读取数据浪费的时间本我们先将所有的基因 序列读取到一个大数组中本一共占用朱朰8杂大小的空间本经测试可以保证内存占用不超过限制朮 采用多线程的方式现在的计算机大都支持多线程的方式运行程序本采用多线程可以充分 利用权材杕资源本提高运行的速度本特别是对于计算量比较大的程序本多线程的优势更加突出朮由 于开始已经将所有的序列读取到内存中本我们可以简单的把数据平均分成李份本每个线程执 行其中的一份本根据实际测试本采用多线程后本对n个每个长度为m的序列求散列值程序的运 行时间可以提高接近朸 倍朮 朳朮朳建立索引的复杂度 朳朮朳朮朱时间复杂度 采用对每个基本操作设定一个时间参数计算时间复杂度。假设散列函数没有发生冲 突。设总的时间为T本读取数据的时间为T1本读取每个字节的平均时间为G1本则T1朽 n m G1；计算所有散列值的时间T2本对杫长序列计算散列值的时间为Tk2本G2是与计算散列值相关 的时间常数，Tk2朽 k G2本根据公式木朳朩计算出的Bk本可得T2朽G2 Bk本T3表示建立散列表的 时间本G3表示插入一条散列值的时间常数本则T3朽 G3 Bk朮 T 朽 T1末 T2末 T3木朵朩 朽 n m G1末 n 木m k 末 朱朩 k G2末 n 木m k 末 朱朩 G3木朶朩 朽 O木nm 末 木nk 末 n朩木m k 末 朱朩朩木朷朩 最坏时间复杂度最坏情况下，插入的每个序列都发生冲突，插入一条散列值得时间不再 是常数，设在散列表中移动一次位置需要G4的时间，则T3朽 Bk(Bk1) 2 G4 T 朽 T1末 T2末 T3木朸朩 朽 n m G1末 n 木m k 末 朱朩 k G2末 n 木m k 末 朱朩 木n 木m k 末 朱朩 朱朩 朲 G4 木朹朩 朽 O木nm 末 木nk 末 n朩木m k 末 朱朩 末 n2木m k 末 朱朩2朩木朱朰朩 朸 朳朮朳朮朲空间复杂度 平均空间复杂度平均空间复杂度由三部分组成：保存序列的空间本散列表占用空间本新分 配的节点占用空间朮假设平均情况下没有冲突。设总的空间为S本保存序列占用的空间为S1本每 个字符占用的空间为M1本则S1朽 M1mn本散列表占用空间大小为S2，每个散列表节点的 大小为M2本则S2朽 M2 H本新分配节点占用的空间为S3本每个新节点占用的空间大小为M3， 则S3朽 朰 M3朮 S 朽 S1末 S2末 S3木朱朱朩 朽 n m M1末 H M2末 朰 M3木朱朲朩 朽 O木nm 末 H朩木朱朳朩 最坏空间复杂度由于保存序列的空间大小和散列表的大小是固定不变的本最坏的情况是 除了第一个序列保存在原散列表下，其余的节点全部保存在新分配的节点中。S1和S2不 变，S3朽 木Bk 朱朩 M3 S 朽 S1末 S2末 S3木朱朴朩 朽 n m M1末 H timesM2末 木n 木m k 末 朱朩 朱朩 M3木朱朵朩 朽 O木nm nk 末 n 末 H朩木朱朶朩 朳朮朴检索的复杂度分析 检索的空间复杂度为O木朱朩朮在理想没有冲突的情况下时间复杂度为O木朱朩本在最坏情况下 所有的序列都保存在某个哈希节点的下面以链表的形式存储，设检索的时间为Q，遍历一 个节点的时间为Q1，则平均需要遍历一半节点数朮 Q 朽 Bk Q1木朱朷朩 朽 n 木m k 末 朱朩 Q1木朱朸朩 朽 O木n木m k 末 朱朩朩木朱朹朩 朳朮朵最大支持的杫值 内存占用最多的情况为申请新节点最多本当杫朽朱本且杄李杁 序列全部相同是本占用的节点 数目最多本此时新申请的空间大小为朷朶朲杍杂木杘朸朶程序朩本朱朱朴朳杍杂木杘朶朴程序朩朮散列表节点申请 的空间大小为 杈未朸杂朽朴朰朶杍杂本保存序列信息的数组占用的空间大小为朹朵杍杂本一共占用的内 存空间大约为朱朶朴朴杍杂木杘朶朴朩本朱朲朶朳杍杂木杘朸朶朩本加上运行时分配的其他空间本该算法可以对所有 的杫朽朱本朲本朮朮朮本朱朰朰建立索引朮 朴模型的检验 根据上面的分析本我们采用杍杵杲杭杵杲杈条杳杨散列函数产生散列值本散列表的大小杈朽朵朳朳朱朲朵朱朷本冲 突解决策咯采用线性探测本建立数据索引本对杫朽朱本朲本朮朮朮本朱朰朰建立数据索引本测得时间和内存占 用下表所示： 朹 图 朱朴机 建立索引的时间与杫的关系曲线 图 朱朵机 内存占用与杫的关系曲线 对于任意的杫 值从样本数据中随机抽取朱朰朰 个，平均的查找并输出的时间为朱杵杳左右， 最长查找及输出时间为朲杵杳 左右。 朵模型的优缺点 该模型利用了散列表检索可以在杏木朱朩时间内完成的性质本建表完成后检索速度非常快本并 根据序列的信息逐步确定散列函数和散列表的参数并进行测试本减少了建立散列表的时间本利 用多线程的方式同步建立数据索引本提高了建表速度朮 该模型是针对给定的样本数据进行设 计的本可移植性差朮在分析时本是按照序列分布完全均匀来做的本尽管样本数据基本符合均匀分 布本对其他分布不均匀的数据没有考虑朮程序中假设不同序列的杈条杳杨 杉杄不会发生冲突本实际 朱朰 中可能会出现相同的情况本会导致检索结果出错朮程序中对数据文件没有检验本认为所有的数 据都是符合要求的朮 朶进一步讨论 对于不均匀序列可以对出现次数较多的序列先求出其在散列表中的位置本预先为其 分配一定的空间本利用数组保存地址信息本一方面可以节省程序运行时的时间本另一方面可以 减少指针占用的内存空间朮 更大数据的检索本模型中样本数据可以直接在内存中处理本如果数据更大无法一次 性在内存中运行本要考虑将计算的结果写入硬盘进行保存本而磁盘的读取性能远不及内存本有 很多可以优化的地方朮 不同的杫值如何一次性的建立索引本模型建立的索引只能对特定的杫进行查询，如果 要求一次建立索引可以用于所有杫值得查询，可以先对较小的杫值建立索引，然后将较长的 序列分割为杫长的序列