A divide-and-conquer approach to fragment assembly

Hasan H. Otu, Khalid Sayood

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


Motivation: 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.

Original languageEnglish (US)
Pages (from-to)22-29
Number of pages8
Issue number1
StatePublished - Jan 1 2003
Externally publishedYes

ASJC Scopus subject areas

  • Statistics and Probability
  • Biochemistry
  • Molecular Biology
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'A divide-and-conquer approach to fragment assembly'. Together they form a unique fingerprint.

Cite this