当前位置：文档之家 › -基于高重复区域基因序列的无模板拼接算法学士学位论文

-基于高重复区域基因序列的无模板拼接算法学士学位论文

  • 格式：doc
  • 大小：1.95 MB
  • 文档页数：63

天津工业大学

毕业论文

基于高重复区域基因序列的无模板拼接算法

姓 名 徐××

学 院 计算机科学与软件

专 业 软件工程

指导教师 陈××

职 称 副教授

2013年5月27日

天津工业大学毕业论文任务书

题目 基于高重复区域基因序列的无模板拼接算法

学生姓名 徐×× 学院名称 计算机科学与软件 专业班级 软件××

课题类型 实际课题

课题意义

利用全基因组无模板拼接技术，可以获得动物、植物、细菌、真菌的全基因组序列，从而推进该物种的研究。一个物种基因组序列图谱的完成，意味着这个物种学科和产业的新开端，这也将带动这个物种下游一系列研究的开展。全基因组序列图谱完成后，可以构建该物种的基因组数据库，为该物种的后基因组学研究搭建一个高效的平台，为后续的基因挖掘、功能验证提供DNA序列信息，为疾病、癌症等的研究提供真实有效的数据。

任务与进度要求 2013.2.20-2013.3.11 选题确认并完成开题报告、任务书的填写、提交、

审核

2013.3.12-2013.3.26 深入了解课题内容、算法分析、确定算法系统框架、熟悉开发工具

2013.3.27-2013.5.3 完成算法的逻辑实现，和算法工具包的开发，完成算法系统的大部分功能，初稿完成

2013.5.4-2013.5.21 进行实验结果整理，并在整理中进一步提高拼接序列的的各项指标，二稿完成

2013.5.22-2013.6.5 毕业论文的审核、修改及定稿并装订

2013.6.6 答辩

主要参考文献 [1] Bresler, M., Sheehan, S., Chan, A.H., and Song, Y.S. Telescoper: De novo

Assembly of Highly Repetitive Regions. ECCB'12 Special Issue,

Bioinformatics[J]. 2012,28 i311-i317

[2] MacCallum,I. et al. ALLPATHS 2: small genomes assembled accurately and

with high continuity from short paired reads[J]. Genome Biol. 2009, 10, R103

[3] Simpson,J.T. et al. ABySS: a parallel assembler for short-read sequence

data[J]. Genome Res. 2009, 19, 1117–1123

[4] Zerbino,D.R. and Birney,E. Velvet: algorithms for de novo short-read assembly

using de Bruijn graphs[J]. Genome Res. 2008, 18, 821–829

[5] Li,R. et al. De novo assembly of human genomes with massively parallel

shortread sequencing[J]. Genome Res. 2010, 20, 265–272

起止日期 2013年2月25日至2013年6月 6日

备注

院长 教研室主任 指导教师

毕业论文开题报告表

2013年3月 8日

姓名 徐×× 学院 计算机科学与软件 专业 软件工程 班级 软件××

题目 基于高重复区域基因序列的无模板拼接算法 指导教师 陈××

一、与本课题有关的国内外研究情况、课题研究的主要内容、目的和意义：

1. 与本课题有关的国内外研究情况

随着新一代基因组测序技术的推广使用，全基因组Shotgun拼接算法和软件得到了广泛的研究。

新一代的基因测序技术像Illumina，Complete Genomics，Helicos，454 Life Sciences，SOLID and Ion Torrent等，测序得到的DNA序列数据相对于第一代测序方法--Sanger测序表现为：高通量、高覆盖率、低成本，与此同时短读长、更多类型的错误，而且普通高等生物的基因组碱基数目巨大，如人类基因组总长约30亿bp，而按新一代的测序技术，一次实验最多只能直接测得不大于1, 000个碱基，另外高等生物的基因还具有非常复杂的重复结构，因而基因组的无模板拼接有很大难度。这样，绝大多数生物的基因组都不能通过实验手段一次性获得，必须借助计算机技术进行后续拼接。自从2005年以后，出现了多种基于下一代测序平台基因序列的从头拼接算法软件包，包括Velvet，ABySS，AllPath，SOAPdenovo等。尽管人们普遍认识到，不同拼接算法所产生的结果具有互补的，但是现在还没有一个方法能融合多个拼接算法的结果。

2. 课题研究的主要内容

基因序列是包含在生物中每个染色体中的DNA碱基序列的集合。基因序列拼接是一个研究如何将包含较短的读长基因数据库中的所有序列通过合并和排序之后拼接成长序列的问题。通常序列拼接的输出是一个称为重叠群（contig）的集合，进而由contigs经过排序、调整、填补间隙等一系列的操作而生成的scaffold序列。

本文提出了一个基于图论的算法，对多个不同算法拼接出的contigs进行拼接，得到更长的scaffold序列。算法首先识别出每对contigs之间的共同片段。然后将达到一定长度的共同片段聚到一个簇中。对于每一个簇，建立一个包含不同contigs之间关系的图结构，最后求解图的最长路径。算法具体步骤如下：

(1) 获得其他算法产生contigs。一部分算法的结果也scaffolds。尽量使用较长的scaffolds。

(2) 为contigs建立索引结构。将每个算法生成的contigs集合建立一个索引结构，生成索引文件。

(3) 利用索引进行映射。根据索引将原始数据库中的全部的基因序列映射到contigs上。 我们规定read-pair中的left read和right read中的部分碱基同时和contig中的某段碱基一致（部分一致，具体的见映射规则），则称为映射成功。映射结果一般表现为：一个contig的不同的位置上有多个read对应。映射规则如下：○1.对contigs中碱基进行数值化。○2.我们只对非ATGC碱基个数不超过碱基序列（read）的5%的read，进行映射。○3.同时对每个read的逆序的碱基互补序列进行映射。○4.我们允许最少2个碱基，最多2%个碱基的错误。○5.我们只分别取出left read前n（要求为取3的倍数）个碱基和right read后n个碱基，组成的有间隙的序列进行映射。

(4) 寻找潜在可拼接的contig对。根据第4步中的映射结果，即每个contig会映射上多个read，多个read组成了集合 (i，基本算法的标识；j，算法结果中contig 编号)。寻找潜在可拼接的contig对是任何两个不同拼接算法中的contig映射到的集合 彼此之间交集的元素个数超过一个给定阈值。

(5) 求最长公共子序列筛选潜在可拼接的contig对。计算第4步中找到的潜在可拼接的两个contigs的最长公共子序列，移除最长公共子序列的长度小于某一阈值的contig对。

(6) 将潜在可拼接的contigs对进行聚簇，簇数记为CCount。

①构建子图，并拼接。将簇中所有,SGij（簇i中的第簇j个子图）合并成能表示一个簇的图CGi（暂且称为簇图，Cluster-Graph），最后求解簇图的最长路径。最长路径所包含的碱基序列即为我们算法拼接之后的结果。

(7) 最终结果的评估。比较各项指标N50、MAX。

结果显示，使用我们的算法，大幅度的增长了的MAX {contigs}。我们也证实了，引进将更多的拼接算法的结果，我们的算法结果将提高的更多。

3. 课题研究的主要的目的和意义

利用全基因组无模板拼接技术，可以获得动物、植物、细菌、真菌、病毒的全基因组序列，从而推进该物种的研究。一个物种基因组序列图谱的完成，意味着这个物种学科和产业的新开端，这也将带动这个物种下游一系列研究的开展。全基因组序列图谱完成后，可以构建该物种的基因组数据库，为该物种的后基因组学研究搭建一个高效的平台，为后续的基因挖掘、功能验证提供DNA序列信息，为疾病、癌症等的研究提供真实有效的数据。

二、进度及预期结果：

起止日期 主要内容 预期结果

2013.2.20-2013.3.11

2013.3.12-2013.3.26

2013.3.27-2013.5.3

2013.5.4-2013.5.21

2013.5.22-2013.6.5

2013.6.6 选题确认并完成开题报告、任务书的填写、提交、审核

深入了解课题内容、算法分析、确定算法系统框架、熟悉开发工具

完成算法的逻辑实现，和工具包的开发，完成算法系统的大部分功能，初稿完成

进行实验结果整理，并进一步提高各项指标，二稿完成

毕业论文的审核、修改及定稿并装订

答辩 完成

完成

完成

完成

完成

完成

完成课题的现有条件 硬件： 曙光小型机(Sugon Server Main Server Chassis)

软件： Vim、Emacs、Gcc/G++、Eclipse、Python、Visual Studio2010

参考文献：

[1] Bresler, M., Sheehan, S., Chan, A.H., and Song, Y.S. Telescoper: De novo

Assembly of Highly Repetitive Regions. ECCB'12 Special Issue,

Bioinformatics[J]. 2012,28 i311-i317

[2] MacCallum,I. et al. ALLPATHS 2: small genomes assembled accurately

and with high continuity from short paired reads[J]. Genome Biol. 2009,

10, R103

[3] Simpson,J.T. et al. ABySS: a parallel assembler for short-read sequence

data[J]. Genome Res. 2009, 19, 1117–1123

[4] Zerbino,D.R. and Birney,E. Velvet: algorithms for de novo short-read

合集下载

基因组组装算法研究报告(综述).doc

基因组组装算法研究报告(综述).doc

基因组组装算法研究报告(综述)

基因组测序是生物信息学的核心，具有极其重要的应用价值。近年来，出现了大量新的测序技术。与传统的桑格方法相比，由这些方法产生的读取(由测序仪直接测量的DNA片段)长度更短，数量更多，覆盖范围更大。然而，传统的拼接算法不适合短阅读的拼接，新拼接算法的拼接效果还有待提高。首先，本文介绍了贪婪算法和重叠算法在传统基因组拼接中的应用。近年来，出现了大量新的测序技术。与传统的桑格法相比，这些方法产生的读数(由测序仪直接测量的DNA片段)长度更短，数量更多，覆盖范围更大。然而，传统的拼接算法不适合短阅读的拼接，新拼接算法的拼接效果还有待提高。首先，本文介绍了贪婪算法和重叠算法:贪婪算法、OLC算法、Deburi JN图算法、HiTEC纠错算法在传统基因组拼接中的应用

一、基因信息重述是生物遗传学和进化的主要研究基础。

能否快速准确地获取生物的遗传信息对生命科学的研究具有重要意义。对于每一个生物体，基因组包含了整个生物体的遗传信息，这通常是由构成基因组的脱氧核糖核酸或核糖核酸分子的碱基对序列决定的。获取目标生物基因组的序列信息，更全面地揭示基因组的复杂性和多样性，已经成为生命科学领域的重要研究内容。确定基因组碱基对序列的过程称为测序。测序技术始于XXXX时代，并随着人类基因组计划的实施取得了快速进展。从第一代到现在广泛使用的第二代，再到近年来出现的第三代，测序技术正朝着高通量和低成本的方向发展。

在现有的测序技术中，根据一定的测序策略，可以获得长度约为50-100个碱基对的序列，称为读长度(read)。基因组的拷贝数约为50-100。基因组组装软件可以根据所有的阅读长度组装成基因组。这些软件的核心是汇编算法。常见的装配算法主要基于OLC(重叠/布局/一致性)法、贪心图法、德布瑞JN图法等。然而，目前可以直接读取的碱基对序列的长度远小于基因组序列的长度，因此有必要使用某些方法将通过测序获得的短片段序列组装成更长的序列。

面向新一代基因组测序技术的序列拼接算法

面向新一代基因组测序技术的序列拼接算法

面向新一代基因组测序技术的序列拼接算法

逯雯雯;卢志远;王亚旭;孙啸

【摘 要】随着新一代测序技术的发展,新的拼接算法应运而生.介绍了目前国际上广泛认可的几种新的拼接算法的基本原理与具体步骤,分析每种算法的优缺点以及适用范围.用Helicobacter acinonychis的Illumina 1G测序数据检测SSAKE,VCAKE,SHARCGS以及velvet的性能,并对未来拼接算法的研究提出展望.

【期刊名称】《生物信息学》

【年(卷),期】2010(008)003

【总页数】6页(P248-253)

【关键词】基因组测序;序列拼接;短片段

【作 者】逯雯雯;卢志远;王亚旭;孙啸

【作者单位】生物电子学国家重点实验室,东南大学生物科学与医学工程学院,南京,210096;生物电子学国家重点实验室,东南大学生物科学与医学工程学院,南京,210096;生物电子学国家重点实验室,东南大学生物科学与医学工程学院,南京,210096;生物电子学国家重点实验室,东南大学生物科学与医学工程学院,南京,210096

【正文语种】中 文

【中图分类】Q78

目前,基因组测序仍然是基因组学的核心内容。基因组测序应用非常广泛,利用它可以获得新物种的基因组序列(从头测序),种群中某个个体的基因组序列(重新测序),从样本中获得 RNA分子序列,以及在分子生物技术中将DNA序列用作读出测定(杂交测序读出变异基因)。其中,获得一个物种的完整基因组序列又是测序的一个最重要的应用。近20年来,随着生物实验技术和信息处理技术的迅速发展与提高,越来越多的模式生物基因组完成了测序。其中,最引人注目的就是人类基因组计划

(Human Genome Project,简称 HGP)。尽管我们已经成功的得到了人类[1],小鼠[2]以及一些其他生物的基因组序列,但是这只是生物圈中成千上万的物种中的很小的一部分。

近 20年来,Sanger测序技术[3]一直是 DNA测序的黄金准则,它能测得 500～1000bp的 read(测序片段,以后简称 read),但是代价昂贵[4]。随着测序技术的革新,测序领域发生了翻天覆地的变化,其中的杰出代表就是 454 Life的焦磷酸测序技术和 Solexa/Illumina的合成测序技术,它们不仅成本更低,而且通量更高、速度更快[5]。相比于 Sanger测序结果,这些技术产生的 read更小,焦磷酸测序可产生200～300bp的 read,合成测序只有 25～36bp,但覆盖深度可达到 100×以上。这些新一代测序技术得到的 read不仅长度短,数量又极为巨大,覆盖度高,这给序列拼接带来了前所未有的难题,而基因组测序中的一个关键的步骤就是序列拼接。测序根据有无参考基因组分为重新测序和从头测序,因此序列拼接也相应分为两类,在这里我们所说的序列拼接都是指对从头测序得到的序列的拼接。传统的拼接算法无法应对这些极短的海量的数据,除此之外,测序过程中产生的错误,以及基因组中重复区域的存在,都成为拼接算法需要攻克的难关,因此,面向新一代测序技术的拼接算法的技术改进迫在眉睫。

基因组序列快速拼接算法及可视化技术的研究的开题报告

基因组序列快速拼接算法及可视化技术的研究的开题报告

基因组序列快速拼接算法及可视化技术的研究的开题报告

题目：

基因组序列快速拼接算法及可视化技术的研究

研究目的：

基因组序列是构成生物体遗传信息的基本单位，对于生命科学研究有着重要的意义。但是，由于生物体基因组大小庞大，序列复杂性高，长序列难以一次性获得，所以需要拼接多个短序列来获得完整的基因组序列。本研究旨在研究基因组序列的快速拼接算法和可视化技术，提高基因组序列拼接的效率和准确性。

研究内容：

1. 研究常用基因组拼接算法，包括Overlap-Layout-Consensus(OLC)算法，De Bruijn Graph(DBG)算法等，分析其优缺点。

2. 基于机器学习理论，结合核酸序列特征，提出一种基于深度学习的基因组拼接算法，可用于拼接不同来源、不同物种的基因组序列。

3. 研究基因组序列可视化工具，以提高对拼接结果的观察、比较、分析和呈现效果。

研究意义：

本研究将提高基因组序列拼接的效率和准确性，提高生物信息学领域研究的可靠性，为基因组学、生物信息学和生命科学研究提供技术支持。

预期成果：

设计一种基于深度学习的基因组拼接算法，结合可视化技术进行验证并实现。 研究方法：

1. 文献资料法：对基因组拼接相关算法、深度学习理论、可视化技术等进行查阅和学习；

2. 数据库法与实验法结合：采用公共数据库中的不同来源、不同物种的基因组序列进行拼接，比较算法效果；

3. 编程实现法：使用Python等编程语言实现算法，结合Javascript等技术实现可视化工具。

研究计划：

第一年：学习基因组拼接相关算法和深度学习理论，初步搭建基于深度学习的基因组拼接算法模型，实现基因组序列自动化分类系统；学习基本的可视化技术，初步设计基于Web的基因组拼接可视化工具。

第二年：研究基于深度学习的基因组拼接算法优化，实现算法的快速和准确；进一步优化基因组拼接可视化工具，加强交互性能，实现联动效果，便于用户操作。

生物信息学在基因组学中的应用

生物信息学在基因组学中的应用

生物信息学在基因组学中的应用

生物信息学是一门交叉学科，结合了生物学、计算机科学和数学，以分析和解释生物数据。随着高通量测序技术的迅速发展，基因组学这一领域得到飞速进展，生物信息学的应用愈加重要。本文将探讨生物信息学在基因组学中的多种应用，包括基因组序列分析、注释与功能预测、变异检测、群体基因组学以及个性化医学等方面。

基因组序列分析

基因组序列的确定是当前生命科学研究的基础。随着下一代测序技术（NGS）的推广，获取完整基因组序列变得日益便捷。然而，海量的序列数据如何高效处理、存储和分析，便成为生物信息学的重要任务之一。

首先，对基因组序列进行质量控制是第一步。使用各类软件，如FastQC等，可以判断出测序数据的质量，滤除低质量序列。接下来，基于序列拼接算法和工具（如SPAdes、Trinity等），对短读段进行拼接，以构建出相对完整的基因组序列。这些工具利用生物信息学算法，在拼接过程中考虑到重复区域和变异点。

接下来的步骤是对拼接完成的基因组进行比对分析。通过使用BLAST、BWA、Bowtie等工具，将新获得的基因组与已有参考基因组进行比对，可以快速识别出保守序列和变异区域。这些分析不仅用于简单的比对，还为进一步的注释和功能研究打下坚实基础。 基因组注释与功能预测

获得基因组序列后，下一步是进行基因组注释，这是指对已获得的基因组中各个功能元件的识别与标记。传统上，这一过程手工完成，但随着计算生物学的发展，许多工具已经能够自动化这一过程。

利用生物信息学工具如AUGUSTUS、Glimmer等，可以通过机器学习算法预测潜在的编码区，并标注出其可能的功能。此外，一般会结合转录组数据进行更准确的注释，这样可以通过RNA-seq获得表达数据，进一步验证基因预测结果。

功能注释通常依赖于比较基因组学的方法，通过比对查找那些已经有功能确立的同源基因，从而推测出新的基因可能具有相似功能。这种方法使得研究人员能够从已知图谱中推断出未知区域的潜在功能，提高了注释效率。