Format

Send to

Choose Destination
See comment in PubMed Commons below
Bioinformatics. 2003 Jan;19(1):22-9.

A divide-and-conquer approach to fragment assembly.

Author information

1
University of Nebraska-Lincoln, Department of Electrical Engineering, 209N WSEC, 68503, USA. otu@eecomm.unl.edu

Abstract

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.

AVAILABILITY:

Available on request from the authors.

PMID:
12499289
[Indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Loading ...
    Support Center