On the complexity of sparse exon assembly

Kent, Carmel; Landau, Gad .M. and Ziv-Ukelson, Michal (2005). On the complexity of sparse exon assembly. In: CPM 2005: Combinatorial Pattern Matching (Apostolico, Alberto; Crochemore, Maxime and Park, Kunsoo eds.), Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, pp. 201–218.

DOI: https://doi.org/10.1007/11496656_18


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. 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 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(n2√n) solution for this case.

Viewing alternatives


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions