Display Settings:

Format

Send to:

Choose Destination
See comment in PubMed Commons below
J Comput Biol. 2000 Feb-Apr;7(1-2):203-14.

A greedy algorithm for aligning DNA sequences.

Author information

  • 1Department of Computer Science and Engineering, The Pennsylvania State University, University Park 16802, USA.

Abstract

For aligning DNA sequences that differ only by sequencing errors, or by equivalent errors from other sources, a greedy algorithm can be much faster than traditional dynamic programming approaches and yet produce an alignment that is guaranteed to be theoretically optimal. We introduce a new greedy alignment algorithm with particularly good performance and show that it computes the same alignment as does a certain dynamic programming algorithm, while executing over 10 times faster on appropriate data. An implementation of this algorithm is currently used in a program that assembles the UniGene database at the National Center for Biotechnology Information.

PMID:
10890397
[PubMed - indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Mary Ann Liebert, Inc.
    Loading ...
    Write to the Help Desk