Published in

Mary Ann Liebert, Journal of Computational Biology, 3(5), p. 493-504

DOI: 10.1089/cmb.1998.5.493

Proceedings of the second annual international conference on Computational molecular biology - RECOMB '98

DOI: 10.1145/279069.279102

Links

Tools

Export citation

Search in Google Scholar

Dynamic Programming Alignment Accuracy

Journal article published in 1998 by Ian Holmes, Richard Durbin ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

Algorithms for generating alignments of biological sequences have inherent statistical limitations when it comes to the accuracy of the alignments they produce. Using simulations, we measure the accuracy of the standard global dynamic programming method and show that it can be reasonably well modelled by an "edge wander" approximation to the distribution of the optimal scoring path around the correct path in the vicinity of a gap. We also give a table from which accuracy values can be predicted for commonly used scoring schemes and sequence divergences (the PAM and BLOSUM series). Finally we describe how to calculate the expected accuracy of a given alignment, and show how this can be used to construct an optimal accuracy alignment algorithm which generates significantly more accurate alignments than standard dynamic programming methods in simulated experiments.