An Almost Quadratic Time Algorithm for Sparse Spliced Alignment

摘要

Abstract The sparse spliced alignment problem consists of finding a chain of zero or more exons from O(n) prescribed candidate exons of a DNA sequence of length O(n) that is most similar to a known related gene sequence of length n. This study improves the running time of the fastest known algorithm for this problem to date, which executes in O(n~(2.25)) time, or very recently, in O(n~2 log~2 n) time, by proposing an O(n~2 log n)-time algorithm.