Login

Publications  •  Project Statistics

Glossary  •  Schools  •  Disciplines
People Search: 
   
Title/Abstract Search: 

Dissertation Information for Sun Kim

NAME:
- Sun Kim

DEGREE:
- Ph.D.

DISCIPLINE:
- Computer Science

SCHOOL:
- University of Iowa (USA) (1997)

ADVISORS:
- None

COMMITTEE MEMBERS:
- None

MPACT Status: Incomplete - Not_Inspected

Title: Amass: A structured pattern matching approach to shotgun sequence assembly

Abstract: "In this thesis, the sequence assembly problem is dealt with. The sequence assembly problem is to reconstruct a DNA sequence from a collection of short DNA fragments taken from random positions by identifying overlaps between the fragments. This problem arises in practice when biologists use shotgun sequencing, a cost-effective method for reading DNA. Existing sequence assembly algorithms have demonstrated limited success in assembling (long) real DNA sequences because they are computationally expensive and fail to properly handle repetitive sequences which are common in real DNA.

We propose an efficient, reliable, shotgun sequence assembly algorithm based on a fingerprinting scheme that is quite robust to both noise and repetitive sequences in the data. Our algorithm uses exact matches of short patterns randomly selected from fragment data to identify fragment overlaps, construct an overlap map, and finally deliver a consensus sequence. We show how statistical clues made explicit in our approach can easily be exploited to correctly assemble results even in the presence of extensive repetitive sequences.

Our approach is exceptionally fast in practice: e.g., we have successfully assembled a whole Mycoplasma genitalium genome (approximately 580 kbps) in roughly 8 minutes of 64MB 200MHz Pentium Pro CPU time from real shotgun data, where most existing algorithms can be expected to run for several hours to a day on the data. In addition, experiments with shotgun data (data is taken from a wide range of organisms, including human DNA) synthetically prepared from real DNA sequences containing extensive repeats demonstrate our algorithm's robustness to repetitive sections in many different sequences. For example, we have correctly assembled a 238kbp Human DNA sequence in less than 3 minutes of 64MB 200MHz Pentium Pro CPU time."

MPACT Scores for Sun Kim

A = 0
C = 1
A+C = 1
T = 0
G = 0
W = 0
TD = 0
TA = 0
calculated 2008-01-31 06:30:34

Advisors and Advisees Graph