Faster exon assembly by sparse spliced alignment

Details Faster exon assembly by sparse spliced alignment Faster exon assembly by sparse spliced alignment

2007-07-23

arxiv.org/abs/0707.3409v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 = \Theta(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}.

Affiliated with

Also associated with

No associations

Rating

Faster exon assembly by sparse spliced alignment does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster exon assembly by sparse spliced alignment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster exon assembly by sparse spliced alignment will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-109919