**Sequence comparison with mixed convex and concave costs**.

D. Eppstein.

Tech. Rep. CUCS-382-88, Computer Science Dept., Columbia University, 1988.

*J. Algorithms*11 (1): 85–101, 1990.Gives an algorithm for finding the minimum number of mutations needed to transform one input string into another, in a general model in which substrings may be inserted or deleted at a cost depending nonlinearly on the substring length. The time bound depends on the number of times the second derivative of the cost function changes sign.

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.