# On the complexity of sparse exon assembly. Academic Article

•
• Overview
•
• Research
•
•
• View All
•

### abstract

• Gene structure prediction is one of the most important problems in computational molecular biology. A combinatorial approach to the problem, denoted Gene Prediction via Spliced Alignment, was introduced by Gelfand, Mironov and Pevzner [5]. The method works by finding a set of blocks in a source genomic sequence S whose concatenation (splicing) fits a target gene T belonging to a homologous species. Let S,T and the candidate exons be sequences of size O(n). The innovative algorithm described in [5] yields an O(n 3) result for spliced alignment, regardless of filtration mode. In this paper we suggest a new algorithm which targets the case where filtering has been applied to the data, resulting in a set of O(n) candidate exon blocks. Our algorithm yields an $$O(n^2 \sqrt{n})$$ solution for this case.

### publication date

• January 1, 2006