DN压缩及模式匹配研究平台

序号： 编码： 第十届“挑战杯”广东大学生课外学术科技作品竞赛作品申报书 作品名称： DNA压缩及模式匹配研究平台 学校全称： 华南农业大学 申报者姓名 （集体名称）： 刘少鹏 类别：自然科学类学术论文 哲学社会科学类社会调查报告和学术论文 科技发明制作A类 科技发明制作B类 说 明1申报者应在认真阅读此说明各项内容后按要求详细填写。2申报者在填写申报作品情况时只需根据个人项目或集体项目填写A1或A2表，根据作品类别（自然科学类学术论文、哲学社会科学类社会调查报告和学术论文、科技发明制作）分别填写B1、B2或B3表。所有申报者可根据情况填写C表。3表内项目填写时一律用钢笔或打印，字迹要端正、清楚，此申报书可复制。4序号、编码由第十届“挑战杯”广东大学生课外学术科技作品竞赛组委会填写。5学术论文、社会调查报告及所附的有关材料必须是中文（若是外文，请附中文本），请以4号楷体打印在A4纸上（文章版面尺寸14.522cm），附于申报书后，论文不超8000字，调查报告不超15000字。6作品申报书须按要求由各校竞赛组织协调机构统一寄送。7其他参赛事宜请向本校竞赛组织协调机构咨询。A1申报者情况（个人项目）说明：1必须由申报者本人按要求填写，申报者情况栏内必须填写个人作品的第一作者（承担申报作品60%以上的工作者）；2本表中的学籍管理部门签章视为对申报者情况的确认。姓 名刘少鹏性别男出生年月1984年9月申报者情况学校全称华南农业大学专 业计算机应用现学历硕士生年级二年级学制 3年入学时间2007年9月作品全称DNA压缩及模式匹配研究平台毕业论文题目通讯地址华南农业大学研究生宿舍6栋904邮政编码510642单位电住地通讯地址广东省潮州市潮安县磷溪镇溪口四村邮政编码521000住宅电话07686705793合作者情况姓 名性别年龄学历所在单位资 格 认定学校学籍管理部门意见 是否为2009年7月1日前正式注册在校的全日制非成人教育、非在职的各类高等院校中国学生（含专科生、本科生和研究生）。是 否若是，其学号为：2007242019（部门盖章） 年 月 日院系负责人或导师意见 本作品是否为课外学术科技或社会实践活动成果 是 否 负责人签名： 年 月 日B3申报作品情况（科技发明制作）说明：1必须由申报者本人填写；2本部分中的科研管理部门签章视为对申报者所填内容的确认；3本表必须附有研究报告，并提供图表、曲线、试验数据、原理结构图、外观图（照片）,也可附鉴定证书和应用证书；4作品分类请按照作品发明点或创新点所在类别填报。作品全称DNA压缩及模式匹配研究平台作品分类（ B ）A机械与控制（包括机械、仪器仪表、自动化控 制、工程、交通、建筑等） B信息技术（包括计算机、电信、通讯、电子等） C数理（包括数学、物理、地球与空间科学等） D生命科学（包括生物、农学、药学、医学、健 康、卫生、食品等） E能源化工（包括能源、材料、石油、化学、化 工、生态、环保等）作品设计、发明的目的和基本思路，创新点，技术关键和主要技术指标一、目的生物信息学(Bioinformatics)是20世纪80年代末随着人类基因组计划的启动而兴起的一门新的交叉学科，其实质就是利用计算机科学和网络技术来解决生物学问题。二十世纪末生物信息学迅速发展，在信息的数量和质量上都极大地丰富了生物科学的数据资源，包括NCBI, EMBL, GDB等DNA数据库的数据量，每年以两到三倍的数量增加。存储DNA数据需要耗费巨大的空间。因此，如何对DNA数据进行压缩，以减少存储空间将是生物学家和计算机专家面临的挑战。通常DNA序列长度可达到上千万个碱基对，并且具有特殊性，仅由A、C、G、T四个字母组成，这导致传统的数据压缩算法在DNA序列压缩效果不理想。于是，必须研究专门针对DNA序列数据的压缩算法：DNA压缩算法。在生物学家对DNA序列数据的使用中，序列比对是生物信息学中最基本、最重要的操作之一。从实现的理论和技术上讲，DNA序列比对的实质是一种特殊的模式匹配，而直接在压缩后的DNA数据上进行序列比对其实质则是一种特殊的压缩模式匹配，即DNA压缩模式匹配。为了更好地研究DNA压缩算法和DNA压缩模式匹配算法，需要建立一个相关的研究平台，即DNA压缩及模式匹配研究平台。该平台主要用于管理和增加DNA压缩算法和DNA压缩模式匹配算法，存储DNA序列数据、DNA压缩数据，能实现各算法效果的比较试验，验证算法有效性，从而为生物信息学研究人员提供方便。二、基本思路采用Java面向对象编程技术，建立一个不依赖具体操作系统的DNA压缩和DNA压缩模式匹配研究的专用平台；并利用该平台，结合DNA序列数据的特点，研究DNA序列数据压缩现有算法和提出新的算法，以有效减少DNA数据所占用的存储空间；研究出专门针对DNA压缩数据的压缩模式匹配算法，以解决在不对DNA序列压缩数据解压缩或最小解压缩的情况下实现序列比对功能。该平台主要由DNA序列获取、DNA序列压缩、DNA压缩模式匹配三大模块组成。在实现中遵循模块化的系统开发原则，使得平台构建符合高内聚、低耦合特点。三、创新点1、可扩展利用面向对象的Java技术而建立的专业的生物信息学研究平台，可持续地开展DNA压缩算法和DNA压缩模式匹配算法的研究。具体地说，平台的可扩展性体现在以下两方面：一是有意义明确的包，尤其是包matching和compress，分别管理匹配和压缩算法，平台使用人员能够自己开发新算法，并加入到其中。二是GUI界面都是用Swing组件写成的，每个面板的功能都是相当明确，其中负责压缩信息处理的CompressPanel和负责模式匹配的MatchingPanel就是很好的体现，它们分别调用包matching和compress里面管理的算法，若平台使用人员需要研究自己开发的新算法，在相应的面板调用即可。举例说明，如果平台需要增加一个新的压缩算法，那么我们要把这个压缩算法设计为一个类，接着把它放到包compress中，再在树状选择压缩算法面板CompressPanel中，为用户增加一个新的选项，即可完成扩展。如果平台需要增加一个新的匹配算法，那么我们要把这个匹配算法设计为一个类，把它放到包matching中，再为用户在树状选择匹配算法面板MatchingPanel增加一个新的选项，即可完成扩展。2、减少DNA序列存储空间参考文本压缩算法思想，根据DNA序列数据特点，研究专门用于压缩DNA序列数据的DNA压缩算法。DNA压缩算法可以高效地压缩DNA序列数据，极大地减少DNA序列数据所占用的存储空间。3、DNA序列比对研究利用压缩模式匹配的思想，根据DNA序列数据的特点，专门研究在对DNA序列压缩数据不解压缩或最小解压缩的情况下，直接在DNA压缩数据中实现DNA的模式匹配，能有效缩短匹配搜索时间，为DNA序列比对研究提供高效率的帮助。目前我们采用多线程技术，设计了基于BM匹配的MTd-BM及MTd-Hosrpool压缩模式匹配等算法，并已将它们集成到平台。4、直接使用压缩DNA数据研究不是把DNA序列数据压缩减小存储空间作为唯一目标，而是把直接有效地利用DNA序列压缩数据作为更重要的目标。四、技术关键1、面向对象的Java技术使得该平台不依赖操作系统和具体机型，因此可运行在小型机、高级服务器、PC台式机、笔记本电脑和Unix、Solaris、Windows和Linux等环境。2、多线程技术在Java中，程序通过流控制来执行程序流，程序中单个顺序的流控制称为线程，多线程则指的是在单个程序中可以同时运行多个不同的线程，执行不同的任务。多线程意味着一个程序的多行语句可以看上去几乎在同一时间内同时运行。3、Swing技术Swing组件被称为轻量级组件，是由纯Java code开发的，它不需要那些关于各种平台的复杂的GUI功能，解决了Java因为窗口类而无法跨平台的问题，并且不会占有太多的系统资源。Swing组件对比AWT组件具有更大强度的可移植性和灵活性。4、Log4j写日志技术Log4j是Apache的一个开放源代码项目，通过使用Log4j，可以对日志信息的级别、输送目的地和输出格式进行控制。具备详细的日志记录功能，才能更好地保证平台的正常运行。五、主要技术指标1、软件平台用户界面友好、可扩展性、可维护性以及健壮性。2、DNA序列数据压缩算法压缩比，该值越小，算法的压缩效果越明显。其计算方法为：DNA序列数据压缩前后的字符总数的百分比值。3、DNA序列压缩模式匹配算法算法运行效率（越快越好）、搜索比较字符操作次数（越少越好）。作品的科学性先进性（必须说明与现有技术相比、该作品是否具有突出的实质性技术特点和显著进步。请提供技术性分析说明和参考文献资料）作品的科学先进性体现在下面四点：1、研究DNA压缩算法和DNA压缩模式匹配算法具有重要意义，该平台为生物信息学相关研究人员的工作提供便捷。开发新算法，再通过平台集成，验证，比较分析一系列处理，研究人员将从中获益。该作品的实质性技术特点和显著进步体现在自己开发的DNA压缩模式匹配算法，已集成在平台上。作者通过平台的使用，能够对开发的新算法与传统算法进行比较分析，并取得一定成果，已分别在中文核心期刊和国际会议发表学术论文两篇。(1) 刘少鹏, 林丕源, 张丽霞, 刘吉平基于多线程技术的d-BM改进算法计算机应用研究, 2008, 25(11): 3299-3301 (中文核心期刊)(2) Lin Piyuan; Liu Shaopeng; Zhang Lixia. Compressed Pattern Matching in DNA Sequences using Multithreaded Technology. The 3rd International Conference on Bioinformatics and Biomedical Engineering (iCBBE 2009), June 11-13th, 2009, Beijing, China. (将被EI检索)2、采用java面向对象编程技术，具有良好的平台无关性及功能可扩展性。3、目前国内外针对DNA压缩算法和DNA压缩模式匹配算法的平台不多。4、参考文献如下，主要有DNA压缩算法和DNA压缩模式匹配算法等国内国外论文，请查阅。1 Don Adjeroh, Yong Zhang, Amar Mukherjee, Matt Powell, Tim Bell, “DNA Sequence Compression Using the Burrows-Wheeler Transform, ” csb, pp.303, IEEE Computer Society Bioinformatics Conference (CSB02), 2002.2 Chen X., Kwong S. and Li M, “A compression algorithm for DNA sequences and its applications in genome comparison”, In Proceedings, 10th Workshop on Genome Informatics (GIW99), pp. 52-61, 1999.3 Ziv J,Lempel A. A Universal Algorithm for Sequential Data Compression J. IEEE Trans. Information Theory, 1977, IT-23(3):337-343.4 Burrows M. and Wheeler D.J, “A block-sorting lossless data compression algorithm”, Technical Report,Digital Equipment Corporation,Palo Alto,CA, 1994.5 Tao Tao, Amar Mukherjee, “Pattern Matching in LZW Compressed Files,” IEEE Transactions on Computers, vol. 54, no. 8, pp. 929-938, Aug., 2005.6 T. Bell, M. Powell, A. Mukherjee, and D. Adjeroh, “Searching BWT Compressed Text with the Boyer-Moore Algorithm and Binary Search”,Proc. Data Compression Conf., pp. 112-121, Apr.2002.7 CHEN Lei, LU Shiyong, RAM J. Compressed Pattern Matching in DNA Sequences: IEEE Computational Systems Bioinformatics Conference, 2004C. Washington, DC: IEEE Computer Society, 2004: 6268.8 BOYER R S, MOORE J S. A Fast String Searching Algorithm J. Communications of the ACM, 1977, 20(10):762772.9 Knuth, D.E., Morris Jr, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal on Computing 6, 323350 (1977)10张丽霞, 张义青, 林丕源, 刘吉平基于字符和0/1码的DNA压缩模式匹配算法计算机应用研究, 2007, 24(9): 22-2411(英)T.K.Attwood, D.J.Parry-Smith 著, 罗静初 等译. 生物信息学概论M. 北京：北京大学出版社, 2002.412Gonzalo Navarro, Mathieu Raffinot 柔性字符串匹配M. 中科院计算所网络信息安全研究组 译. 北京: 电子工业出版社, 2007.313生物信息学智能化算法及其应用M. 王翼飞 史定华主编. 北京: 化学工业出版社, 2006.5作品在何时、何地、何种机构举行的评审、鉴定、评比、展示等活动中获奖及鉴定结果华南农业大学2009年“挑战杯”校内大学生课外学术科技作品竞赛二等奖作品所处阶 段（ ）A实验室阶段 B中试阶段 C生产阶段D 平台可初步应用，辅助DNA压缩算法及压缩模式匹配算法研究 （自填）技术转让方式作品可展示的形 式 实物、产品 模型 图纸 磁盘 现场演示 图片 录像 样品使用说明及该作品的技术特点和优势，提供该作品的适应范围及推广前景的技术性说明及市场分析和经济效益预测一、使用说明平台已制作成exe安装文件，用户运行该exe文件即可进行安装。成功安装后，即可点击桌面快捷方式启动平台，接着按照下面的步骤依次进行操作：读入DNA、读入Pattern、压缩DNA、压缩Pattern、模式匹配、报告算法分析结果。二、技术特点和优势界面友好，流程固定，具有易操作性和实用性；支持使用者进行二次开发；详细的日志记录保证可维护性；目前国内外同类型的平台不多，因此具有一定优势。三、适用范围及推广前景DNA压缩算法及其DNA压缩模式匹配算法的研究，有助于将DNA序列数据从较为高端的工作平台(专用的存储容量较大的服务器)迁移到更简易的工作平台(普通的存储容量较小的计算机，如笔记本电脑或PDA)上，使得生物学家可以随时随地开展研究工作；DNA压缩算法及其DNA压缩模式匹配算法的研究，还可以为在普通工作平台上建立专门的二级数据库提供新的方法。由于DNA数据库的数据量在以每年两到三倍的数量增加，因此将来使用压缩的DNA数据会成为必然的趋势，而要直接使用DNA压缩数据，DNA压缩模式匹配又是必须解决的问题。因此DNA压缩和DNA压缩模式匹配就有良好的应用前景。四、市场分析和经济效益预测该平台比较专注，研究机构和高校的生物信息学相关研究人员是平台的潜在用户。通过二次开发，平台使用者还可以进行新算法的设计实现，并集成到平台，再与传统算法比较分析，从而获得更优算法。该平台将对科研工作起到良好的辅助作用，具有一定的经济效益。专利申报情况提出专利申报 申报号 申报日期 年 月 日已获专利权批准 批准号 批准日期 年 月 日 未提出专利申请科研管理部门签 章 年 月 日C.当前国内外同类课题研究水平概述说明：1.申报者可根据作品类别和情况填写；2.填写此栏有助于评审。DNA数据量巨大，并且由于其具有特殊性，只包含A、T、C、G四个字符，使得应用传统的压缩算法效果不理想。为了更好地对DNA数据进行压缩，减小DNA数据所占用的空间，计算机专家经过多年不断努力，开发了多个专门针对DNA数据的压缩算法。1993年Grumbach S.和Tahi F.从经典的基于字典压缩的LZ系列算法中提出BioCompress算法，从搜索和编码两方面针对DNA序列进行改进。1999年Chen X., Kwong S.和Li M.对BioCompress算法进行改进，提出GenCompress算法，使得序列数据压缩的速度和压缩率提高到实用层次。2001年Sato H., Yoshioka T., Konagaya A.和Toyoda T.提出Cfect算法，引入后缀树数据结构，提高搜索重复字符串速度，并提高序列数据的压缩率。2002年，Chen X., Li M., Ma B.和Tromp J.以生物数据序列比对为基础，提出DNACompress算法，获得了较高数据压缩率。2005年Kordi, G.和Tabus, I.， Sheng Bao, Shi Chen, Zhiqiang Jing和Ran Ren，Jie Liu, Sheng Bao, Zhiqiang Jing和Shi Chen均尝试进一步改进算法，提高DNA数据的压缩率。压缩模式匹配(Compressed pattern matching)思想于1992年由Amir和Benson首先提出，即给定文本T，根据某种压缩算法进行压缩得到压缩串Z，给定模式串P，仅仅使用P和Z寻找P在T中的所有出现。因为DNA序列数据及其压缩算法的特殊性，DNA压缩模式匹配算法也需要进行专门研究，以具有更好的适应性。DNA压缩模式匹配是生物信息学中一个新的研究领域，主要致力解决下面的问题：对给定的压缩格式的DNA序列文件F和一个DNA模式P，在不解压缩或最小解压缩的情况下找出P在F中所出现的位置。2004年CHEN Lei, LU Shiyong在BM算法的基础上，提出d-BM压缩模式匹配算法；2005年Tao Tao, Amar Mukherjee提出基于LZW算法的压缩模式匹配算法。通过近年来对IEEE、Elsevier、Springer、ISI Web of Science等重要数据库和生物化学与生物物理学报、自然科学进展(PROG NAT SCI)、Biological Reviews、Bioscience、Biological Bulletin等杂志的跟踪检索，不难发现：由于研究的难度和复杂性，国内外有关DNA压缩模式匹配的研究工作开展得不多，只有极少的报道。因此，开展DNA压缩模式匹配算法与DNA压缩算法研究同样是有重大意义的。 D.推荐者情况及对作品的说明说明：1由推荐者本人填写；2推荐者必须具有高级专业技术职称，并是与申报作品相同或相关领域的专家学者或专业技术人员（教研组集体推荐亦可）；3推荐者填写此部分，即视为同意推荐；4推荐者所在单位签章仅被视为对推荐者身份的确认。推荐者情况姓 名刘才兴性别男年龄45职称教授工作单位华南农业大学信息学院通讯地址广州市天河区五山路483号邮政编码510642单位电宅电荐者所在单位签章刘才兴老师是教授，硕士生导师，情况属实。 （签章） 年 月 日请对申报者申报情况的真实性作出阐述该平台已有软件安装版本，可以运行。请对作品的意义、技术水平、适