Dissertation > Excellent graduate degree dissertation topics show

Based on Euler path parallel DNA sequence assembly

Author: ChenDaChun
Tutor: RenShiJun
School: Harbin Institute of Technology
Course: Computer Science and Technology
Keywords: Euler path de Bruijn Figure Parallel DNA splicing Hash map
CLC: Q78
Type: Master's thesis
Year: 2010
Downloads: 196
Quote: 0
Read: Download Dissertation

Abstract


DNA sequences spliced ​​genome sequencing is one of the core issues . From 1977 Sanger sequencing technology invented beginning to 2005 second-generation sequencing technology came this time , DNA sequencing using the Sanger sequencing technology major . Sanger DNA sequencing fragment length measured to achieve 1000bp, and 99.999% can be achieved only . Sanger sequencing technology resulting DNA fragments usually overlap - Ordering - generation algorithm splicing consensus sequences . Compared with the first generation sequencing technology , the second generation measured by sequencing the DNA fragment having a length shorter , the error rate is high, and flux characteristics. The characteristics of these sequences , the second -generation sequencing technologies are currently three splicing strategies: greedy algorithm , overlap - Ordering - generate consensus sequence algorithm, and based on de Bruijn graph Euler path algorithm . These three in the first two need to calculate the consensus sequence of all DNA fragments with high time complexity. Based on de Bruijn graph algorithm will read Euler path split into k-mer DNA was spliced ​​into question Euler path problem. Euler path problem there is a linear time algorithm . In this paper, as Euler path algorithm for DNA sequence assembly algorithms. The second -generation high -throughput sequencing technology . The second generation sequencing technology in a single run can produce a few G -byte read data , mosaic algorithm based on de Bruijn Tu Oula space will face a bottleneck . This paper describes a de Bruijn graph based parallel stitching algorithm, which will be read through the split generated k-mer stored in multiple processes distributed hash table , and the k-mer encoding reduces memory consumption. DNA splicing parallel execution , and by sending and receiving packets between the various splicing processes to share data . Experimental results show that the parallel stitching algorithm has nearly linear time complexity and space complexity, which has a good scalability, able to solve large-scale genome sequence assembly problem .

Related Dissertations

  1. Research on De Bruijin Graph for DNA Sequence Assembly,Q523
  2. Full Custom Design and Realization of High-Performance Memory of X Processor,TP333
  3. Chinese Word Auto-segmentation Design and Algorithm Realization for Chinese Network Information Retrieval,TP391.3
  4. Research and Implementation on Knowledge Representation of Gene Regulatory Network,Q78
  5. Research on Combinatorial Regulation of Multiple Transcription Factors,Q78
  6. Research on Graph-Based Algorithm for Tagsnps Selection,Q78
  7. The Expression of Let-7 microRNA during the Process of the Mouse Embryonic Lung Development and the Construction of the Adenovirus Shuttle Plasmid,Q78
  8. Expression of hBMP4 and hBMP7 in Chinese Hamster Ovary Cells,Q78
  9. Directed Evolution of Lipase from Penicillium Expansum FS1884 by Error Prone PCR,Q78
  10. Protein phosphatase 2A Cα subunit knockout cardiac energy metabolism due to remodeling,Q78
  11. Gene Prediction and Sequence Analysis of Insect OBP CSP and sid-1,Q78
  12. Cloning and Expression of Xylanase Gene from Thermobifida Halotolerans YIM 90462~T,Q78
  13. The Preliminary Study on Interleukin-10 Transgenic Mice,Q78
  14. miR - 23 in mouse skeletal muscle expression and the regulation of skeletal muscle regeneration research,Q78
  15. Studies on Construction of Specific Gland Expressional Vector of HLF and Modified Fibroblast Cell Line,Q78
  16. Improvement in Electroporation Transformation Efficiency of Gene for Bacillus Subtilis with Trehalose,Q78
  17. Cloning and Expression of Organic Solvent Tolerant Lipase Gene from Staphylococcus Saprophyticus M36,Q78
  18. Expression of Glucose Oxidase Gene from Aspergillus Niger Z-25 in Pichia Pastoris,Q78
  19. Prokaryotic Expression and Purification of Human Beta-Defensin-9,Q78
  20. Molecular Cloning, Prokaryotic Expression and Characterization of a Novel Trypsin Inhibitor in the Frog, Lepidobatrachus Laevis,Q78
  21. Construction of Engineering Strain Saccharomyces Cerevisiae Metabolizing Xylose,Q78
  22. Study on the Correlation of murA Gene and Mycobacterial Growth,Q78

CLC: > Biological Sciences > Molecular Biology > Genetic engineering (genetic engineering)
© 2012 www.DissertationTopic.Net  Mobile