（计算机系统结构专业论文）dna数据存储与比对技术研究.pdf

摘要 随着d n a 分析技术的发展与应用的不断深入，d n a 数据的存储与访问【 益 成为关注的焦点。一般应用系统采用现有的数据库系统来进行管理，数据库系统 区别于其它系统的重要方面之一是d b m s 具有有效地处理非常大量数据的能力， 但是随着d n a 数据量的增长，数据的检索速度日益捉襟见肘，如何提高数据的 检索效率逐渐受到重视，特别是在一些特殊领域对数据的实时性要求较高的情况 下，更需要快速的数据检索。本文正是基于此考虑，针对d n a 数据的特点及实 际比对的需要，通过具体的数据库实现技术，分析了存储结构对数据库访问速度 的影响。在此基础上通过对给出的几个具体的存储方案及相应的比对算法的实际 测试，得到一个相对较优的解决方案。并依此建立了数据比对系统，该系统是采 用j 2 e e 应用服务器技术设计的三层b s 体系结构。 关键词：存储结构检索效率d n a 比对多维定位辅助检索结构 a b s t r a c t t h e s t o r a g ea n d a c c e s so fd n ad a t ah a v e b e e n p a i dm o r e a t t e n t i o nt oi n c r e a s i n g l y a l o n g w i t ht h ed e v e l o p m e n ta n d a p p l i c a t i o no f d n aa n a l y s i st e c h n o l o g y c o m m o n l y ， a p p l i c a t i o n s u s ed a t a b a s et om a n a g et h ed n ad a t a o n eo f i m p o r t a n c ea s p e c t so f d b m s ，d i f f e r e n t f r o m o t h e r s ，i st h a th a sac a p a b i l i t yo f p r o c e s s i n gv e r yl a r g eq u a n t i t i e s o fd a t a b u tw i t hd n ad a t a i n c r e a s i n gi nq u a n t i t y t h e r e h a v et o om a n y p r o b l e m st o d e a lw i t ht h er a t eo f d a t as e a r c h e s i th a sb e e n g i v e n m o r ea t t e n t i o n g r a d u a l l yt oh o w t o i m p r o v e t h ee f f i c i e n c yo f d a t a s e a r c h e s e s p e c i a l l yi ns o m e a r e a st h a th a v em o r ed e m a n df o rr e a lt i m ep r o p e r t yr a t eo fd a t as e a r c h e sa r er e q u i r e dg r e a t l y j u s tb a s e do nt h i s p o i n tt h i sd i s s e r t a t i o nm a i n l yd i s c u s s e sa b o u t d a t as t o r a g eo f d n a ，a n d a n a l y s e st h e e f f e c to fs t o r a g es t r u c t u r e st ot h er a t eo fd a t as e a r c h e si na l l u s i o nt oc h a r a c t e r i s t i c s o f d a t ao f d n aa n d r e q u i r e m e n t so f d n am a t c h i n g i np r a c t i c eb y a p p l y i n g t h et e c h n o l o g yo f d a t a b a s ei m p l e m e n t a t i o n o n i tt h ed i s s e r t a t i o ns h o w sa r e l a t i v e l yb e s ts o l v e o f d a t a b a s es t o r a g es t r u c t u r e sa n d c o r r e s p o n d i n g m a t c hm e t h o d b yt e s t i n gs o m ep r o j e c t s a c c o r d i n g t oi t ，t h i sd i s s e r t a t i o np r e s e n t sad a t am a t c h s y s t e m w i t hj 2 e e a p p l i c a t i o n s e t - - v e rt e c h n o l o g yi nt h r e et i e r so f b sa r c h i t e c t u r e k e yw o r d ：s t o r a g e s t r u c t u r e ss e a r c h e se f f i c i e n c yd n am a t c hm u l t i - d i m e n s i o n o r i e n t a t i o n a u x i l i a r ys e a r c h e ss t r u c t u r e s 创新性声明 y 5 8 3 3 5 1 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所列的内容外，论文中不包 含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：堡垒日期：星竺! ：! 关于论文1 吏用授权说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权属西安电子科技大学。本人保证毕业离 校后，发表论文或使用论文工作成果时署名仍然为西安电子科技大学。学校有权 保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分 内容，可以允许采取影印、缩印或其他手段保存论文。( 保密的论文在解密后遵守 此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：4 壅鳖日期：塑午，牛 导师签名 曰j 胡：丝型：型 第一章绪论 第一章绪论 1 1 课题的来源与背景 课题选自国家公安部法庭科学d n a 数据库管理系统中的核心部分。这是 由珠海黑马医学仪器有限公司承接公安部的个重点计算机软件开发项目，泰坦 软件系统有限公司作为二级开发商承接黑马公司的软件设计、开发。 d n a ( 脱氧核糖核酸) 分析应用于法医学鉴定是近十年来的事，目前发现的 d n a 多态位点越来越多，分析技术越来越精巧、简便、快速、经济和实用。d n a 分析的法医学应用使以往只能检测基因编码的酶或蛋白质水平飞跃到直接检查基 因的分子水平，这是法学物证检验史上的一场重大的革新。由于p c r 能够在短时 间内扩增靶d n a 至百万拷贝，使生物性检材鉴定的灵敏度得以空前的提高，特 别是s t r - p c r 复合扩增技术，它的个别识别率可达到百亿分之一，灵敏度达到 0 1 n gd n a 即1 u 1 血斑，非常适用于微量及腐败物证的检验。继d n a 指纹后，p c r 被誉为第二代d n a 分型技术，短短几年中，p c r 技术已在法医物证鉴定中迅速 得以推广和应用。而相关d n a 数据的有效存储及快速的数据比对方法的研究与 数据库的前沿技术紧密结合，针对d n a 数据的特点，提出了一些比较有价值的 方案，并应用到实际检测中。 1 2 课题的现实意义 所选课题的目的是改进d n a 数据的存储结构，优化查询建立高效的比对算 法，提高d n a 基因数据查询速度及效率，使其更好地适应实际应用的需要。其 具有极其重要的现实意义，速度和效率的提高，应用d n a 技术进行个体识别和 网络技术，便可在全国范围内迅速鉴别罪犯身份，为快速破案、缉捕罪犯提供有 力保障，特别有利于打击流窜作案、重复犯罪等罪犯。对维护社会稳定，改善治 安环境有着重要作用。 1 3 课题研究内容分析 影响d n a 数据库访问速度的限制因素，主要有三个方面：1 、数据库本身的 结构及数据的存储方式；2 、数据库接口的访问策略及其效率；3 、硬件资源的约 束。( 其他的方面还能涉及到网络连接等) 针对以上主要的限制因素，我们可以采 2d n a 数据存储于比对技术研究 取相应的解决策略。首先对于第一个方面，应建立与d n a 数据特点相适应的存 储结构，并在其基础上采用快速的比对算法，优化查询。对于第二个方面，主要 考虑采用有效的接1 ：3 访问机制，建立快速并行处理策略，使得接口在大规模访问 的情况下，能够维持一个稳定、高效的性能。不至于使数据库压力过大而效率降 低，查询访问速度下降。对于第三个方面，比较好解决。可以利用d b m s 的增强 功能，如：s q l s e r v e r2 0 0 0 的群集服务器。另外只是简单地增加硬件冗余，就可 以大大提高数据访问速度。再有，多机系统也是可以考虑的，如图1 1 所示。 d b ld b 2d b 3 r e l l | l o t ej e r m i n a l 图1 1 多机系统 由上面的解决策略我们可以看到，课题进展分三个阶段。第一个阶段，完成 对d n a 数据存储结构及相应的比对算法的设计草案。下一步对这个初步解决方案， 进行单机测试。建立对应存储结构的数据库，对每一种结构，使用不同的查询策 略及比对算法进行测试，然后对结果数据进行分析比较，得到一个相对较优的方 案。 第一章绪论 1 4 课题的主要研究内容、研究目标 建立有效的d n a 数据的存储方案，依据方案设计高效快速的数据比对方法， 并对方案进行实际测试。根据测试结果构建一个相对较优的解决方案，按此方案 完成初步的软件原型。 “法庭科学d n a 数据库管理系统”是管理d n a 样品和人员背景资料，以及 上传、比对等管理信息的数据库应用系统，系统采用b s 结构。该系统应用对象 是公安系统的国家、省厅( 3 1 个) 以及地区以上的市局等三级机构，国家、省厅、 市局三级结构中的每个有建立d n a 基因数据库条件的单位，独立建立数据库， 独立建立网站。应用的群体是d n a 实验室的工作人员和管理人员，以及广大的 公安系统人员。 分级结构如图1 2 所示。 图1 2 分级结构 数据库系统采用s q l s e r v e r 2 0 0 0 数据库管理系统。其数据分布是样品数据除 本市局d n a 样品数据库保留外，必须逐级上传。对于本市局未建立d n a 数据库 f 的情况下，样品数据直接传送到省厅的数据库，再上传到国家库。 1 5 论文安排 论文共分为六章，各章的内容安排如下： 第一章绪论：本章主要介绍了课题的来源与背景、课题的现实意义课题研究 内容的分析，以及课题的主要研究内容与研究目标。 第二章数据存储：本章主要介绍了存储器层次，数据库系统结构，数据库的 设计方法以及d b m s 中的数据存储。 第三章d n a 数据存储方案；本章主要介绍了d n a 数据，d n a 数据的存储及 存储方案设计。 第四章d n a 数据比对：本章首先介绍了基因数据比对的相关概念，然后根据 第三章设计的存储方案进行比对算法的设计。 4 d n a 数据存储于比对技术研究 第五章测试与结果分析：本章对前两章所设计的方案进行了测试与分析，包 括：测试方案说明、测试平台介绍、测试步骤以及测试结果分析。 第六章数据比对系统：本章介绍了演示系统的架构，包括三层结构原理、比 对系统架构及系统相关技术。其中与系统实现相关的技术主要有j 2 e e 应用服务器技术、s e r v l e t 、j s p 、j a v a b e a n 、7 d b c 以及数据库存储过 程。 第二章数据存储 第二章数据存储 数据存储的概念是伴随着计算机技术的发展而发展的，体现了数据管理技术的 发展，经历了人工管理、文件系统、数据库系统三个阶段。这里主要研究的是数 据库管理系统( d b m s ) 中对数据的存储管理。 2 1 存储器层次 目前，在典型的计算机系统中作为数据存储载体的存储器，其存储容量的范 围至少有7 个数量级，相应的访问速度的范围也有7 个或超过7 个数量级。每个 字节价格也各不相同，但与容量和访问速度相比相差不大，最便宜的与最贵的大 约相差3 个数量级。事实上，具有最小容量的设备提供最快的访问速度，其每个 字节的价格也最高。其层次结构如图2 1 所示。 丁) r m s 第二级 图2 1 存储器层次 高速缓冲存储器：c a c h e ，处于存储器层次的最低层，是一种集成电路( “芯 片”) ，或者是处理器芯片的部分，它能存放有限的数据和机器指令。目前，典 型的高速缓存的容量达到1 m 字节以上，高速缓存与处理器之间数据的读写可以以 处理器指令的速度执行，通常为1 0 n s ( 1 0 8 秒) 或更少。另一方面，在高速缓存与 主存之间移动指令或一个数据项的时间则要长得多，大约要1 0 0 n s ( 1 0 4 秒) 。 主存储器：简称主存，又称内存，是计算机的活动中心。计算机中，不论是 指令的执行还是数据的操纵，都是作用于驻留在主存中的信息上的，尽管实际上 通常将所使用的数据移到高速缓存中( 如上所述) 。至今，普通的机器配置为1 2 8 m d d r 或2 5 6 md d r 主存，更大容量主存的机器，如1 0 g b 以上的也能找到。主存 d n a 数据存储于比对技术研究 是随机访问的，这意味着在同一时间内可以获得任何一个字节。从主存访问数据 的典型时间通常是在1 0 l o o n s ( 1 0 4 1 0 1 秒) 范围内。 虚拟存储器：在写程序的时候，我们所使用的数据( 如，程序变量、要读取 得文件等) 都要占据一个虚拟的存储器地址空间，同样，程序指令也占据一个它 们自己的地址空间。对于使用3 2 位字长的机器大约有2 3 2 个或者说4 0 亿个不同 的地址。由于每个字节都需要自己的地址，我们可以认为典型的虚拟存储器为 4 g b 。由于虚拟存储器空间比通常的内存要大的多，一个完全被占用的虚拟存储器 的大部分内容实际上时保存在硬盘上。通常，硬盘被逻辑地分成多个块( b l o c k ) ， 大小在和5 6 k b 的范围内。虚拟存储器以整个块为单位在硬盘和主存之间移动，主 存中的这些块被称作页( p a g e ) 。机器硬件和操作系统允许虚存页进入主存的任 何部分，并且使得块中的每一个字节都被它的虚拟地址正确地指向。 第二级存储器：( s e c o n d a r ys t o r a g e ，辅助存储器，简称辅存) ，是存储器的一 种形式，它的速度要比内存慢得多，而存储容量则比内存大得多，并且基本上是 随机访问。这里讨论的第二级存储器主要是指硬盘，硬盘被认为是既支持虚拟存 储器，也支持文件系统。这就是说，有些磁盘块在被用于保存一个应用程序的虚 拟存储器页面的同时，另一些磁盘块被用于保存( 部分) 文件。2 0 0 3 年，微型机 所使用的i d e 接口的硬盘单碟容量已达到8 0 g b ，整个硬盘的容量已超过2 0 0 g b 以上。由上分析可知，第二级存储器的速度比典型的内存慢1 0 5 倍，而容量则至少 比典型的内存大1 0 0 0 倍以上，其价格也明显地要比内存便宜的多。 第三级存储器：( t e r t i a r ys t o r a g e ) 主要用于保存以太( 1 0 1 2 ) 字节计数的数据 容量。与第二级存储器相比，其读写时间要长的多，大约要慢1 0 0 0 倍，也就是毫 秒与秒的比值；但是其容量比磁盘大得多，大约相差也是近1 0 0 0 倍，也就是太字 节与吉字节的比值；每个字节花费则比磁盘更少。 存储器层次中各个级别的访问时间与容量之间的关系，用双对数度量结果如图 2 2 所示。 2l0- l- 2- 3- 45 6- 7- 8- 9( 1 02 ) 秒 图2 2 存储器层次中各个级别的访问时间与容量的关系 心n潞盯：宝 第二章数据存储 这里所讨论的数据存储是指d b m s 的数据存储，而d b m s 的特性之一就是支 持数据的持久性，即当机器断电后也耍能保持数据，因此数据就应当保存在非易 失的存储设备上。对于以上所讨论的各层次存储器来说，高速缓存、主存储器都 是易失部件，不能作为数据的持久存储，因而只有第二级存储器与第三级存储器 符合要求，考虑到检索速度的需要，这里只对第二级存储器中的硬盘进行讨论。 2 2 数据库系统结构 数据库系统结构可以由多种不同的层次或不同的角度，这主要依据观察者。 如果从数据库管理系统角度看，数据库系统通常采用三级模式结构，这是数据库 管理系统的内部结构；如果从数据库最终用户角度看，数据库系统的结构分为集 中式结构( 又可有单用户结构、主从式结构) 、分布式结构、客户，服务器结构和并 行结构，这是数据库系统外部的结构。 虽然实际的数据库管理系统产品种类很多，他们支持不同的数据模型，使用 不同的数据库语言，建立在不同的操作系统之上，数据的存储结构也各不相同， 但它们在体系结构上通常都具有相同的特征，即采用三级模式结构并提供两极映 象功能。数据库系统的三级模式结构是指构成数据库系统的外模式、模式和内模 式，如图2 3 所示。 图2 3 数据库系统的三级模式结构 模式( s c h e m a ) ：是数据库中全体数据的逻辑结构和特征的描述，是所有用户 的公共数据视图。它是数据库系统模式结构的中间层，即不涉及数据的物理存储 细节和硬件环境，也与具体的应用程序，与所使用的应用开发工具及高级程序设 计语言无关。模式实际上是数据库数据在逻辑级上的视图。 8 d n a 数据存储于比对技术研究 外模式( e x t e r n a ls c h e m a ) ：也称子模式或用户模式，是数据库用户( 包括应 用程序员和最终用户) 能够看见和使用的局部数据的逻辑结构和特征韵描述，是 数据库用户的数据视图，与某一应用有关的数据的逻辑表示。 内模式( i n t e r n a ls c h e m a ) ：也称存储模式( s t o r a g es c h e m a ) ，一个数据库只 用一个内模式，它是数据物理结构和存储方式的描述，是数据在数据库内部的表 示方式。如，记录的存储方式是顺序存储、按照b 树结构存储还是按l l a s h 方法存 储；索引按照什么方式组织；数据是否压缩存储，是否加密；数据的存储纪录结 构有何规定等。 数据库系统的三级模式是对数据的三个抽象级别，他把数据的具体组织留给 d b m s 管理，是用户能逻辑地抽象地处理数据，而不必关心数据在计算机中的具 体表示方式与存储方式。为了能够在内部实现这三个抽象层次的联系和转换，数 据库管理系统在这三级模式之间提供了两层映象： 外模式，模式映象：模式描述的是数据的全局逻辑结构，外模式描述的是数据 的局部逻辑结构。对应于同一个模式可以有任意多个外模式。对于每一个外模式， 数据库系统都有一个外模式模式映象，它定义了该外模式与模式之间的对应关系。 这些映象定义通常包含在各自外模式中的描述中。当模式改变时( 例如增加新的 关系、新的属性、改变属性的数据类型等) ，由数据库管理员对各个外模式模式的 映象作相应改变，可以使外模式保持不变。应用程序是依据数据的外模式编写的， 从而应用程序不必修改，保证了数据与程序的逻辑独立性，简称数据的逻辑独立 性。 模式，内模式映象：数据库中只有一个模式，也只有一个内模式，所以模式内 模式映像是唯一的，它定义了数据库全局逻辑结构与存储结构之间的对应关系。 例如，说明逻辑记录和字段在内部是如何表示的。该映象定义通常包含在模式描 述中。当数据库的存储结构改变了( 例如选用了另一种存储结构) ，由数据库管理 员对模式内模式映象作相应改变，可以使模式保持不变，从而应用程序也不必改 变。保证了数据库的三级模式结构中，数据库模式即全局逻辑结构是数据库的中 心与关键，它独立于数据库的其他层次。因此设计数据库模式结构适应首先确定 数据库的逻辑模式。数据存储的设计涉及到的内模式是依赖于它的全局逻辑结构， 但独立于数据库的用户视图即外模式，也独立于具体的存储设备。它是将全局逻 辑结构中所定义的数据结构及其联系按照一定的物理存储策略进行组织，以达到 较好的时间与空间效率。 数据库的外模式面向具体的应用程序，它定义在逻辑模式之上，但独立于存储 模式和存储设备。当应用需求发生较大变化，相应外模式不能满足其视图要求时， 该外模式就得做相应改动，所以设计外模式时应充分考虑到应用的扩充性。 特定的应用程序是在外模式描述的数据结构上编制的，它依赖于特定的外模 第二章数据存储 式，与数据库的模式和存储结构独立。不同的应用程序有时可以共用同一个外模 式。数据库的二级映象保证了数据库外模式的稳定性，从而从底层保证了应用程 序的稳定性，除非应用需求本身发生变化，否则应用程序一般不需要修改。 数据与程序之间的独立性，使得数据的定义和描述可以从应用程序中分离出 去。另外，由于数据的存取由d b m s 管理，用户不必考虑存取路径等细节，从而 简化了程序的编制，大大减少了应用程序的维护和修改。 这里主要讨论的是如何根据应用的需要，建立与模式相应的内模式，提高数据 的检索效率。 2 3 数据库的设计方法 数据库的设计方法比较有名的是新奥尔良方法。他将数据库设计过程分为四个 阶段：需求分析、概念设计、逻辑设计和物理设计。 需求分析 主要工作是确定用户达到什么样的目标，从这些目标中得出数据库的要求。并 把这些要求整理成说明书，应该包括数据流程图、约束条件、技术指标等信息。 以后的工作都是遵循需求分析结果进行，因此对于复杂的数据库应该格外重视这 个环节。 ， 概念设计 概念设计的目标是产生反映企业组织信息需求的数据库概念结构，概念设计的 主要方法是采用e r 方法。就是确定实体和关系。 逻辑设计 逻辑设计的目标是，从概念模型导出特定的数据库逻辑模式，这些模式在功能、 性能、完整性和一致性约束及数据库可扩展性等方面均应满足用户提出的要求。 这一步要做e r 图向关系模型转换的工作。 物理设计 数据库的物理设计，是从一个满足用户信息需求的、已确定的逻辑数据库结 构，研制出一个有效的、可实现的物理数据库结构的过程。在物理设计时要考虑 数据库的性能等面向最终用户的东西。这个过程也是要生成一个物理设计说明书， 我们在实现数据库时就是根据这个说明书一步一步做的。 2 4 加嬲中的数据存储 d b m s 中的数据存储主要是考虑数据库的内模式，即数据如何组织，如何确定 一个行之有效韵存储调度算法。在大多数算法研究中，人们假设，数据是在主存 l o d n a 数据存储于比对技术研究 储器中，对任何数据项的访问所花费的时间与访问其他任意数据项一样多。这种 计算模式通常被称为计算的“r a m 模型”，或者随机访问的计算模型。然而，当 实现个d b m s 时，必须假设，数据不是装载主存储器中。因此，在所涉及的有 效的算法中，必须考虑使用第二级存储器，或许甚至要考虑使用第三级存储器。 在第二级存储器或第三级存储器中处理极大量数据的最佳方法，通常不同于处理 同样问题的最佳主存储器算法。 在设计算法时，将主要考虑主存储器与第二级存储器之间的相互作用，注意 限制磁盘访问次数是有好处的，即使这种算法对主存中数据的操作动作并不是对 主存的最好方法。这里将使用磁盘i 0 的数目作为衡量每个操作的代价的标准，这 个衡量标准与前面讨论一个观点是一致的，即从磁盘中得到数据的时间比对内存 中的数据做任何有用操作花费的时间都长。主要的例外情况是在回答查询需要通 过网络进行数据通信对。 每一个应用程序都包含一些输入和输出。大部分都是使用文件来保存它们的 输入和输出数据( 至少是一部分) 。对于应用程序的开发、维护和运行成本而言，对 i o 的数据结构和算法的选择可能是至关重要的。拙劣的数据结构会导致代码不易 开发和维护，文件不易管理。拙劣的算法将使应用程序的执行性能被文件的i o 操 作所限制。错误或者说不合理的算法可能使应用程序的运行速度比正常情况慢 1 0 0 0 倍。应用程序的性能常常是由输入和输出的代价决定。让文件结构技术支持 关系数据库所需要的主要能力是按内容有效地访闯记录。大多数关系操作需要从 数据表中找出满足某些条件的行。 计算机磁盘是旋转的设各，它分为柱面、磁道和扇区。系统软件( 包括操作 系统以及本文所讨论的关系数据库管理系统) 中的文件管理系统是把磁盘组织成 顺序的系列字节，建立从文件视图( f i l ev i e w ) 到硬件视图( h a r d w a r ev i e w ) 的 映射，即磁盘被组织成磁盘页，每一也包含有相同数量的扇区，文件被组织成一 些磁盘页的有序集合，作为一个文件的磁盘页在物理上可能保持连续也可能不连 续而通过链接指针组织在一起，这取决于系统软件对不同文件类型管理的需要。 对于这里所讨论的数据库管理系统对数据的存储一般采用如下几种方式。 2 4 1 不包含索引的顺序存储 数据库管理系统中，依据用户的要求对于一些数据存储不建立索引，只是顺序 的存储在数据库中。这种存储的组织方式根据数据的类型和使用的方式的不同， 可以采用以上的两种方式，即连续存储和不连续存储。这里需要注意的是存储方 式的连续和不连续是指硬件视图下的磁盘页在硬盘磁道位置上的扇区是否连续， 即是否在同一磁道或相邻磁道是连续的扇区。这样存储的数据在需要检索特定键 第二章数据存储 值记录的时候必须顺序查找，效率较低，对于特定范围检索效率会有所改善，一 般系统会建立临时的索引或根据统计量来提高检索效率，但效果并不是很明显。 另外对于数据的更新操作( u p d a t e ) 比较困难，需要消耗大量的系统资源与时间。 这种存储方式适合于那种对记录改动较少的数据存储，特别是一些流媒体数 据。另外其他索引存储方式的数据文件基本采用这种方式。 2 4 2 以内容为基础的简单索引存储 实现关系数据库管理系统的一个根本问题是有效地执行查询。在大多数场合， 查询处理包括查找满足选择规则的数据行，也就是属性中含有特定数值的行。最 一般的情形是必须通过主键选出某一行，因此需要建立主键索引。一个简单的索 引是一列键值对，当数据文件打开要进行数据访问等操作时，需先查找索引以取 得键值的引用，然后根据引用作为数据文件的地址来读取数据记录，因此索引必 须是惟一索引。这种存储方式对于小数据量还是很实用的，当数据量增大到索引 文件不能完全读入到内存中时，简单索引就不是很有效。 2 4 3 二级索引 除了使用主键访问记录外，有时还需要使用其它字段来访问记录。一个二级索 引文件是这样的个文件，它的键不是数据文件的主键。二级索引一般不要求键 是惟一的。这样的一个索引必须为每一个键维护- - n 索引。一个二级索引文件可 以设计成使用主键值作为引用，把每个非主键值与包含这个非主键值的记录的主 键建立对应关系。在记录发生变更时，这种二级索引的组织方法把维护索引的代 价控制到最小程度。按这种方式查找一个数据记录，要求在二级索引中查找期望 的值，再从查找结果相应的主键索引中找出引用值，然后使用这个引用值作为数 据记录的地址。 2 4 4 多级索引和b + 树 多级索引，简单地讲就是索引的索引，是对索引文件再建立索引。b + 树实际 上也是一种数据文件的多级索引，是按某种规则建立起来的，是由索引节点构成 的一棵多级别的平衡树。多级索引形成了数据文件的一棵平衡树，每一个非叶子 级别是数据文件的一列排序链接列表记录，他们用作为树的下一个更低级别索引 记录的索引。b + 树的叶子级别时数据文件的一列排序联结索引。b + 树的插入和删 除操作保证了树的平衡型。b + 树的重要的方面是它可以保证非常快的查找时间， 即便是对非常大的文件也是如此。这样的一个索引可以用不超过3 次的磁盘读取 d n a 数据存储于比对技术研究 操作访问一个含有10 0 00 0 0 条记录的数据文件。索引文件也可以快速地进行更新。 一个索引顺序文件由一个排序的数据文件和一棵b + 树索引组成，数据文件是一列 排序的数据块，这种数据存储方式对应与数据库管理系统中所建立的簇索引。 2 4 5 散列表表示索引的存储 散列运算指的是把属性值直接环转换成地址的过程，散列表索引中每一个键 引用对存储在散列表中的一个特定位置。散列表中的键引用对的地址是通过散列 函数计算而得。一个散列表把一个索引表示位一组存储桶，存储桶中的所有键有 相同的或类似的散列值。同其他索引一样，一个散列表索引是一列键，引用对。散 列表一般提供了比b + 树索引更快的查找速度，但它不能用于模糊查询和限定范围 的查询，因为这样的一个索引不是一列排序键。查找一个散列表索引要求首先把 一个搜索键转换成一个整数值，把这个整数传到散列函数中，计算出散列值，使 用值个散列值确定存储桶地址，最后在存储桶中找出所要的地址。散列的一个主 要优点是它可以用于任意大的搜索键，这个搜索键可能有多个属性串联而成。 一个加了索引的文件由一个数据文件加上一个或多个相关的索引文件组成。 为了能在一个加了索引的文件中读取一个具有特定键值的记录，可以先查找索引 文件取得这个键值的引用，然后使用这个引用作为数据文件的地址，读取一个数 据记录。在一个加了索引的文件中执行记录的插入、更新和删除操作时，需要更 新索引文件。 第三章d n a 数据存储方案 第三章d 数据存储方案 在数据库管理系统中，d n a 数据的存储是对数据库内模式( 存储模式) 的设计。 存储器为第二级存储器即硬盘介质，数据库管理系统采用m i c r o s o f t 公司的s q l s e r v e r2 0 0 0 。 3 1d n a 数据 系统所采用的d n a 数据是把样品检测得到的基因型转化为的数字表示。在有 性繁殖的生物体中，d n a 作为遗传物质包含了生物体的遗传信息，它记载在d n a 链上，但不是所有的片段都包含这种遗传信息。在人类基因d n a 链上包含了遗传 信息的位置( 片段) ，都有国际标准的命名，称为基因座名称，就是所采样分析的 位点。等位基因是指在测定人群中相同位点上碱基对r g b t 重复次数所构成的有 限集合。如d 3 s 1 3 5 8 位点其等位基因集合共有8 个等位基因，分别是1 2 、1 3 、1 4 、 1 5 、1 6 、1 7 、1 8 、1 9 。两等位基因组成一个基因型，如1 2 1 7 这个基因型，表示 d 3 s 1 3 5 8 位点的分型结果高基因座值为1 2 ，低基因座值为1 7 ，两个值一起代表了 该位点的一个分型结果数据，也就是系统中所存储的数据。d n a 数据在每一位点 的等位基因域是个有限的集合，所以由等位基因中任意两个( 包括相同等位基 因组合，其称为纯合子，不同则称为杂合子) 组合构成的位点数据是一个有限的 集合。 目前主要有两家公司的仪器作d n a 测试，其为a b i ( p e ) 公司和p r o m e g a 公 司，他们提供的位点序列稍有不同，如a b i “冒) 公司( 1 5 爹岔席) ： c s f l p o ，d 1 3 s 3 1 7 ，d 1 6 s 5 3 9 ，d 1 8 s 5 1 ，d 2 1 s 1 l ，d 3 s 1 3 5 8 ，d 5 s 8 1 8 ，d 7 s 8 2 0 ， d 8 s 1 1 7 9 ，f g a ，t h 0 1 ，t p o x ，v w a ，旦2 s 1 3 3 8 ，d 1 9 s 4 3 3 ；艘o m e g a 公司( 1 5 个位点) ：c s f l p o ，d 1 3 s 3 1 7 d 1 6 s 5 3 9 。d 1 8 s 5 1 。d 2 1 s l l 。d 3 s 1 3 5 8 d 5 s 8 1 8 。 d 7 s 8 2 0 ，d 8 s 1 1 7 9 ，f g a ，t h e 0 1 ，t p o x ，v w a ，p e n t a d ，p e n t a e ；其中，下划 线为不同位点。实际可采用的位点包括以上两家公司仪器所做出的，共有2 5 个之 多。 3 2d n a 数据的存储 为了适应实际比对系统的需要，d n a 数据的存储结构要有利于提高检索效率。 目前一些系统采用的是将d n a 样品数据、涉案相关人员背景资料及案件信息作为 一个关系，存储到一个表中。这样做的目的主要是简化存储结构，有利于系统实 现，但同时带来的问题是当数据量增加时，检索速度会随之有明显地下降。下面 是一个常见例子的表结构：( 如表3 1 ) 1 4d n a 数据存储于比对技术研究 字段名说明类型长度 备注 c l p s数值 1 60 d n 0 0记录顺序号数值 1 60 d n 0 1数据库类型字符 2 0索引、提示 d n 0 2基因类型 字符2 0索引、提示 d n 0 3上报状态字符 1 0提示 d n 0 4入库状态字符 1 0提示 d n 0 5关联分型数据字符 1 0 0索引 d n 0 6分类字符 1 0 0分类 d n 0 7复核标记 字符1 0 0 d n 0 8备用字符 2 00 d n 0 9备用字符 2 0 0 d _ n 1 0备用字符 5 ( 1q d n l la 吼字符 5索引 d n l 2位点1 a 字符1 0 o d n l 3位点i b字符 1 00 d n l 4位点2 a 字符1 0 0 d n l 5位点2 b字符 1 0 0 d n 6 0位点2 5 a字符 1 00 d n 6 l位点2 5 b字符 1 0o d n 6 2备用 字符2 6 0 d n 6 3备用字符 2 00 d n 6 4备用字符 2 0 0 d n 6 5备用字符 5 0 i 0 表3 1 该表结构在典型的数据库应用系统中应该说是理所当然的结构，然而问题在 于我们的应用系统对数据有不同的使用目的及检索要求和项目。在进行d n a 数据 比对时，比对的是位点数据，而与之相关的背景信息并不是检索的重点，相对比 较可以忽略。在这个例子中，一条数据记录的全部属性结构所占用的存储空间是 1 0 0 7 b ，对于d n a 数据比对的有用位点信息数据为5 0 5 b ，只占全部数据结构存储 空间的5 0 ，其他信息包括备用字段占了剩余的部分。就目前来说两家公司机器 所能做出的位点信息加起来才只有1 7 个，占用空间为3 4 0 b ，所占空间只有1 3 多 一点，也就是说能提供有用检索的数据只占很少一部分。更重要的是我们所关心 的数据除了性别位点a m e l 外( 此位点对比对检索数据基本没什么贡献) ，其它并 没有加上索引这对大数据量检索来说是不能接受的。 下面看看数据是如何存储的。这里以s q l s e r v e r 2 0 0 0 数据库管理系统为例， 第三章d n a 数据存储方案 该关系中记录顺序号是主健，然而在其上并没有建立任何索引。根据规定，其他 的索引项中只能有个是簇索引，余下的为非簇索引。在这里我们关心的是d n a 数据，所以这些索引对我们的检索基本上是毫无裨益的。s q ls e r v e r2 0 0 0 数据的 页大小为8 k b ，页头是9 6 个字节长，包含了页的类型信息、可用空间及页的属主 对象的i d 。数据一次一行地被加入数据库，每一行只能存放在一个数据页中。因 此，每行数据的最大长度是8 0 9 6 个字节，这里不包括文本、非文本或图像数据。 这个结果是8 k b 的数据页减去9 6 个字节的页头得出的结果。如果保持7 5 的填 充因子的话，那么实际可用于存储的页空间是6 0 7 2 个字节长。而我们这个关系的 元组存储结构的大小为1 0 0 7 个字节，那么一页只能存储6 条记录( 8 0 9 6 * 7 5 1 0 0 7 】) 。如果是1 0 0 万条数据的话，那么就需要大约 c ： ! 尘 8 b j 。( 其中j l j 2 ，j m 属于 1 ，2 ，n ) 目前n 值是2 5 ，实际检测数 只有1 7 个位点) 。 b j l 专b j 2 专b j m 舌。正连厂。乏卜+ 毗对结果集， 图4 2 2 、取位于比对序列第一位置的父母位点，对其高低位点值进行组合 获得一个位点值集。分别取此集合中的组合值，在登记表b i l 中( 如 表5 1 ) 进行查询，得到已在登记表中注册的组合值集合及其对应 记录的主键集合 k i l ，并将其作为第二步比对集按照比对序列 依次取父母位点值进行组合，然后对比对集进行筛选最终得到 满足最大相异位数的比对结果集 k i 。 。其可能为空或非空，非空 是全部比对结束找到匹配记录，为空可能进行了全部比对也可能是 中间比对集为空，跳出比对丽结束，没有匹配记录。对于有匹配的 d n a 数据存储于比对技术研究 情况，我们转到程序3 ，否转到程序4 。 3 、根据比对的最终结果集中的主键值，读取原表记录。该程序要用到 b + 树索引或者是散列表索引( 如果有原表记录引用就可以直接读取 记录) 。 4 、返回最终结果。( 为空或者是结果记录集) ( 子女) 1 、同上： 2 、取位点比对序列第一位置的子女位点，分别以高低位点值在登记表 琶l 中( 如表3 9 或表3 1 0 ) 查询，得到已在登记表中注珊的包含该 位点高( 或低) 基因座值的值集及其对应记录的主键集合，根据亲 源标志字段q 确定一个匹配去杂的双亲( 单亲) 集吃低l ，并将其作 为第二步比对集按比对序列的顺序依次取子女位点分高低基因 座值进行筛选最终得到满足最大相异位数的比对结果集鹕。 。 其可能为空或非空，非空是全部比对结束找到匹配记录，为空可能 进行了全部比对也可能是中间比对集为空，跳出比对而结束，没有 匹配记录。对于有匹配的情况，我们转到程序3 ，否转到程序4 。 3 、根据比对的最终结果集中的主键值，读取原表记录。该程序要用到 b + 树索引或者是散列表索引( 如果有原表记录引用就可以直接读取记 录) 。 4 、返回最终结果。( 为空或者是结果记录集) 这样在确定比对序列后。根据第一位置数值的大小来决定使用原表还是使用视 图，如果数量很小的话直接读原表效率会更高一些。我们还可以考虑增加冗余的 方法进一步改造方案。 第五章铡试与结果分析 第五章测试与结果分析 为了比较各个方案实际数据库查询比对速度，从而得到一个相对较优的存储 策略以及相应的比对算法，对于上面提出的方案，分别进行了测试： 5 1 溯试方案 5 1 1 澜试内容： 分别测试在数据量为：1 0 0 0 0 、1 0 0 0 0 0 、1 0 0 0 0 0 0 下9 及1 5 位点的比对查询 索引使用情况 执行计划 数据物理存储效率 查询i 0 开销( 包括扫描计数、逻辑读、物理读、预读情况) c p u 占用时间( 分析编译时间、读取缓存时间、查询执行时间) 5 1 2 测试平台： 软件：操作系统w i n d o w s 2 kp r o f e s s i o n a l 、d b m ss q l s e r v e r2 k 、查询分析器 硬件：c p u c e l e o n1 7 g i o o m h z 、内存2 5 6 md d r 、硬盘4 0 0 5 4 0 0 r m 测试用例：( 参见实施方案) 5 1 3 测试步骤t 1 、建立数据库 2 、建立各方案所需的数据表、视图及索引等 3 、生成测试数据 4 、测试各比对算法方案 5 、结果数据整理 5 2 测试结果分析 以下的测试结果都是在查询分析器中测得的，为了适应一定的存储结构，我 们采用了相应的比对算法。为了更清楚地说明问题，我们对原方案也进行了测试， 将其作为评价其它方案优劣的标准。 表5 1 为9 个位点的测试数据，表5 2 为1 5 个为点的测试数据( 单位：毫秒) 。 为了使测试数据更有说服力，我们分别采样了首、中、尾记录及无记录进行测试， 然后取平均值。在每一次的测试过程中我们使用d b c cd r o p c l e a n b u f f e r s 与d b c c f r e e p r o c c a c h e 系统命令清除系统缓冲区及过程高速缓存，以此来达到致的测试 初始环境。在此前提下我们设置s e ts t a t i s t i c s1 0o n 及s e ts t a t i s t i c st i 溉o n 命令项，来获得有关磁盘活动数量的详细信息与每一语句在解析编译以及执 d n a 数据存储于比对技术研究 行时所需要的时间。这里我们主要针对i 0 0 万条记录数据，进行了详细的比较测试 加上了分析编译时间及i 0 开销，具体测试结果见( 表5 3 、表5 4 ) 。 测试项目1 万数据量l o 万数据量t o f l 万数据璧 方案 c p i j 时间查询耗时c p u 时间查询耗时c p u 时间查询耗时 原方案2 36 4 6 2 2 55 4 7 32 9 8 56 1 8 8 6 方案一 1 02 3 91 9 62 2 8 82 2 5 02 9 7 3 2 方案二 2 26 3 22 8 15 5 1 82 9 9 15 8 7 6 5 方案三 i 01 92 02 52 87 l 方案盯 1 01 55 5 2 11 4