A 3-Approximation Algorithm for the Multiple Spliced Alignment Problem and Its Application to the Gene Prediction Task

摘要

The Spliced Alignment Problem is a well-known problem in Bioinformatics with application to the gene prediction task. This problem consists in finding an ordered subset of non-overlapping substrings of a subject sequence g that best fits a target sequence t. In this work we present an approximation algorithm for a variant of the Spliced Alignment Problem, called Multiple Spliced Alignment Problem, that involves more than one target sequence. Under a metric, this algorithm is proved to be a 3-approximation for the problem and its good practical results compare to those obtained by four heuristics already developed for the Multiple Spliced Alignment Problem.