Faster exon assembly by sparse spliced alignment
| dc.creator | Tiskin, Alexander | |
| dc.date | 2007-07-23 | |
| dc.date.accessioned | 2026-07-07T08:19:43Z | |
| dc.date.available | 2026-07-07T08:19:43Z | |
| dc.description | Assembling a gene from candidate exons is an important problem in computational biology. Among the most successful approaches to this problem is \emph{spliced alignment}, proposed by Gelfand et al., which scores different candidate exon chains within a DNA sequence of length $m$ by comparing them to a known related gene sequence of length n, $m = Θ(n)$. Gelfand et al.\ gave an algorithm for spliced alignment running in time O(n^3). Kent et al.\ considered sparse spliced alignment, where the number of candidate exons is O(n), and proposed an algorithm for this problem running in time O(n^{2.5}). We improve on this result, by proposing an algorithm for sparse spliced alignment running in time O(n^{2.25}). Our approach is based on a new framework of \emph{quasi-local string comparison}. | |
| dc.identifier | https://arxiv.org/abs/0707.3409 | |
| dc.identifier | http://arxiv.org/abs/0707.3409 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134857 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | Computational Engineering, Finance, and Science | |
| dc.subject | Quantitative Methods | |
| dc.title | Faster exon assembly by sparse spliced alignment | |
| dc.type | text |