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

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

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI