The Chain Alignment Problem

摘要

This paper introduces two new combinatorial optimization problems involving strings, namely, the Chain Alignment Problem, and a multiple version of it, the Multiple Chain Alignment Problem. For the first problem, a polynomial-time algorithm using dynamic programming is presented, and for the second one, a proof of its NP-hardness and in approximability are provided, jointly with the main ideas of three heuristics proposed for it. The three heuristics are assessed with simulated data and the applicability of both problems here introduced is attested by their good results when modeling the Gene Identification Problem. (C) 2020 Elsevier B.V. All rights reserved.