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

About

• Item ORO ID
• 80090
• Item Type
• Conference or Workshop Item
• ISBN
• 978-3-540-31562-9 / 978-3-540-26201-5
• ISSN
• 0302-9743
• Academic Unit or School
• Faculty of Wellbeing, Education and Language Studies (WELS)
• Copyright Holders
• © 2005 Springer-Verlag Berlin Heidelberg
• Depositing User
• Carmel Kent