2008/09/09 by Peter Huggins, Ruriko Yoshida, Huggins, Peter +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computational Geometry and Mesh Generation #FOS: Biological sciences #Gene expression and cancer classification #Populations and Evolution (q-bio.PE)
paper · pdf · doi:10.48550/arxiv.0809.1473
openalex publication_date 2008/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Optimal sequence alignments depend heavily on alignment scoring parameters. Given input sequences, \em parametric alignment is the well-studied problem that asks for all possible optimal alignment summaries as parameters vary, as well as the \em optimality region of alignment scoring parameters which yield each optimal alignment. But biologically correct alignments might be \em suboptimal for all parameter choices. Thus we extend parametric alignment to \em parametric k-best alignment, which asks for all possible k-tuples of k-best alignment summaries (s1, s2, ..., sk), as well as the \em k-best optimality region of scoring parameters which make s1, s2, ..., sk the top k summaries. By exploiting the integer-structure of alignment summaries, we show that, astonishingly, the complexity of parametric k-best alignment is only polynomial in k. Thus parametric k-best alignment is tractable, and can be applied at the whole-genome scale like parametric alignment.