Shotgun Sequence Assembly

TitleShotgun Sequence Assembly
Publication TypeBook Chapters
Year of Publication2004
AuthorsPop M.
Book TitleAdvances in ComputersAdvances in Computers
VolumeVolume 60
PublisherElsevier
ISBN Number0065-2458
Abstract

Shotgun sequencing is the most widely used technique for determining the DNA sequence of organisms. It involves breaking up the DNA into many small pieces that can be read by automated sequencing machines, then piecing together the original genome using specialized software programs called assemblers. Due to the large amounts of data being generated and to the complex structure of most organisms' genomes, successful assembly programs rely on sophisticated algorithms based on knowledge from such diverse fields as statistics, graph theory, computer science, and computer engineering. Throughout this chapter we will describe the main computational challenges imposed by the shotgun sequencing method, and survey the most widely used assembly algorithms.