A Chaining Algorithm for Mapping cDNA Sequences to Multiple Genomic Sequences

摘要

Given a set of matches between a cDNA sequence and multiple genomic sequences, we present a subquadratic chaining algorithm for computing an optimal chain of colinear matches, while allowing overlaps between the matches. Our algorithm improves upon the quadratic graph based solution, and extends the previous algorithms which are limited to matches between a cDNA sequence and a single genomic sequence. The matches of the resulting chain serve as anchors for computing a multiple alignment between the cDNA and the given sequences.