Academic Commons

Reports

Sequence Comparison with Mixed Convex and Concave Costs

Eppstein, David

Recently a number of algorithms have been developed for solving the minimum-weight edit sequence problem with non-linear costs for multiple insertions and deletions. We extend these algorithms to cost functions that are neither convex nor concave, but a mixture of both. We also apply this technique to related dynamic programming algorithms.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-382-88
Published Here
December 21, 2011