Efficiently detecting polymorphisms during the fragment assembly process.
BACKGROUND
Current genomic sequence assemblers assume that the input data is derived from a single, homogeneous source. However, recent whole-genome shotgun sequencing projects have violated this assumption, resulting in input fragments covering the same region of the genome whose sequences differ due to polymorphic variation in the population. While single-nucleotide polymorphisms (SNPs) do not pose a significant problem to state-of-the-art assembly methods, these methods do not handle insertion/deletion (indel) polymorphisms of more than a few bases.


RESULTS
This paper describes an efficient method for detecting sequence discrepencies due to polymorphism that avoids resorting to global use of more costly, less stringent affine sequence alignments. Instead, the algorithm uses graph-based methods to determine the small set of fragments involved in each polymorphism and performs more sophisticated alignments only among fragments in that set. Results from the incorporation of this method into the Celera Assembler are reported for the D. melanogaster, H. sapiens, and M. musculus genomes.
Fasulo
Daniel
D
Informatics Research, Celera Genomics, 45 W. Gude Dr., Rockville MD 20850, USA. daniel.fasulo@celera.com
Halpern
Aaron
A
Dew
Ian
I
Mobarry
Clark
C
D000465:Algorithms; D001483:Base Sequence; D016384:Consensus Sequence / Q000235:genetics*; D053938:DNA Fragmentation / Q000235:genetics*; D020869:Gene Expression Profiling / Q000379:methods*; D014644:Genetic Variation; D008969:Molecular Sequence Data; D011110:Polymorphism, Genetic / Q000235:genetics*; D012150:Polymorphism, Restriction Fragment Length; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*