On the complexity of sparse exon assembly

Kent, Carmel; Landau, Gad M. and Ziv-Ukelson, Michal (2006). On the complexity of sparse exon assembly. Journal of Computational Biology, 13(5)

DOI: https://doi.org/10.1089/cmb.2006.13.1013

Abstract

Gene structure prediction is one of the most important problems in computational molecular biology. It involves two steps: the first is finding the evidence (e.g., predicting splice sites) and the second is interpreting the evidence, that is, trying to determine the whole gene structure by assembling its pieces. In this paper, we suggest a combinatorial solution to the second step, which is also referred to as the "Exon Assembly Problem." We use a similarity-based approach that aims to produce a single gene structure based on similarities to a known homologous sequence. We target the sparse 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.

Viewing alternatives

Look up in Google Scholar

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

  • Item ORO ID
  • 80079
  • Item Type
  • Journal Item
  • ISSN
  • 1013-1027
  • Keywords
  • exon assembly; rectilinear Steiner arborescence; sequence alignment; dynamic programming
  • Academic Unit or School
  • Faculty of Wellbeing, Education and Language Studies (WELS)
  • Copyright Holders
  • © 2006 Mary Ann Liebert, Inc.
  • Depositing User
  • Carmel Kent
CORE (COnnecting REpositories)

Recommendations