title: A divide-and-conquer approach to fragment assembly.
abstract: BACKGROUND
  One of the major problems in DNA sequencing is assembling the fragments obtained by shotgun sequencing. Most existing fragment assembly techniques follow the overlap-layout-consensus approach. This framework requires extensive computation in each phase and becomes inefficient with increasing number of fragments.
  
  
  RESULTS
  We propose a new algorithm which solves the overlap, layout, and consensus phases simultaneously. The fragments are clustered with respect to their Average Mutual Information (AMI) profiles using the k-means algorithm. This removes the unnecessary burden of considering the collection of fragments as a whole. Instead, the orientation and overlap detection are solved efficiently, within the clusters. The algorithm has successfully reconstructed both artificial and real data.
  
  
  BACKGROUND
  Available on request from the authors.
authors.affiliation: University of Nebraska-Lincoln, Department of Electrical Engineering, 209N WSEC, 68503, USA. otu@eecomm.unl.edu
authors.forename: Hasan H
authors.initials: HH
authors.lastname: Otu
authors.forename: Khalid
authors.initials: K
authors.lastname: Sayood
mesh_terms: D000465:Algorithms; D000818:Animals; D033481:Chromosomes, Mammalian / Q000235:genetics; D016000:Cluster Analysis; D003198:Computer Simulation; D016384:Consensus Sequence / Q000235:genetics; D004247:DNA / Q000235:genetics*; D053938:DNA Fragmentation / Q000235:genetics*; D051379:Mice; D011119:Polynucleotides / Q000235:genetics; D011786:Quality Control; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
chemical_list: D011119:Polynucleotides; D004247:DNA