Copy the page URI to the clipboard
Kent, Carmel; Landau, Gad .M. and Ziv-Ukelson, Michal
(2005).
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 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
Metrics
Public Attention
Altmetrics from AltmetricNumber of Citations
Citations from DimensionsItem Actions
Export
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