My Bachelor Thesis

Abstract

A new big challenge in computational biology is the mapping of large numbers of short oligonucleotide reads to a reference genome while allowing a few errors. This thesis describes a method applied in the successful Eland tool to solve this problem and attempts an implementation in SeqAn, a bioinformatical C++ library.

Download

• The thesis
• The tool’s code

Note: The code is still subject to change because of lacking documentation.

References

• AMD Advanced Micro Devices Inc., Software optimization guide for AMD Athlon™ 64 and Opteron™ processors, 2005.
• Simon T. Bennett, Colin Barnes, Anthony Cox, Lisa Davies, and Clive Brown, Toward the 1,000 dollars human genome., Pharmacogenomics 6 (2005), no. 4, 373–382 (eng).
• S. Burkhardt and J. Kärkkäinen, Better Filtering with Gapped q-Grams, Fundamenta Informaticæ 56 (2003), no. 1, 51–70.
• Francis S. Collins, Michael Morgan, and Aristides Patrinos, The human genome project: lessons from large-scale biology., Science 300 (2003), no. 5617, 286–290.
• Andreas Döring, David Weese,Tobias Rausch, and Knut Reinert, SeqAn – An efficient, generic C++ library for sequence analysis, BMC Bioinformatics 9 (2008), no. 1, 11.
• Ruiqiang Li, Yingrui Li, Karsten Kristiansen, and Jun Wang, SOAP: short oligonucleotide alignment program., Bioinformatics (2008).
• Samuel Levy, Granger Sutton, and J. Craig Venter, The diploid genome sequence of an individual human., PLoS Biol 5 (2007), no. 10, e254 (eng).
• U. Manber and G. Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms (1990), 319–327.
• Catherine Shaffer, Next-generation sequencing outpaces expectations, Nature Biotechnology 25 (2007), 149.
• Jay Shendure, Robi D. Mitra, Chris Varma, and George M. Church, Advanced sequencing technologies: methods and goals., Nat Rev Genet 5 (2004), no. 5, 335–344.
• Bjarne Stroustrup, C++ programming styles and libraries, January 2002.
• Caroline Stupnicka, Solexa announces progress in its single molecule array technology at bioarrays europe conference, 10 2002.
• T. F. Smith and M. S. Waterman, Identification of common molecular subsequences., JMol Biol 147 (1981), no. 1, 195–197 (eng).
• The C++ Standards Committee, Working Draft, Standard for Programming Language C++, Tech. report, ISO, 05 2008.
• J. Craig Venter, Knut Reinert, et al., The sequence of the human genome, Science 291 (2001), no. 5507, 1304–1351.
• Ben Werther and Damian Conway, The Design and Implementation of SPECS: An alternative C++ syntax, Tech. report, Department of Computer Science, Monash University, 2000.
• Robert H. Waterston, Kerstin Lindblad-Toh, Ewan Birney, and Eric S. Lander, Initial sequencing and comparative analysis of the mouse genome., Nature 420 (2002), no. 6915, 520–562 (eng).

The thesis is licensed under the Creative Commons by-nc license 3.0.
The code is part of the SeqAn library and thus licensed under the terms of the Lesser GNU Public License.