Skip to Main content Skip to Navigation
Conference papers

Finding Nested Common Intervals Efficiently

Abstract : In this paper, we study the problem of effi ciently fi nding gene clusters formalized by nested common intervals between two genomes represented either as permutations or as sequences. Considering permutations, we give several algorithms whose running time depends on the size of the actual output rather than the output in the worst case. Indeed, we first provide a straightforward O(n^3) time algorithm for finding all nested common intervals. We reduce this complexity by providing an O(n^2) time algorithm computing an irredundant output. Finally, we show, by providing a third algorithm, that fi nding only the maximal nested common intervals can be done in linear time. Considering sequences, we provide solutions (modi cations of previously de ned algorithms and a new algorithm) for di fferent variants of the problem, depending on the treatment one wants to apply to duplicated genes.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620365
Contributor : Guillaume Blin <>
Submitted on : Saturday, October 22, 2011 - 9:02:36 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Thursday, November 15, 2012 - 10:20:37 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620365, version 1

Citation

Guillaume Blin, Jens Stoye. Finding Nested Common Intervals Efficiently. 7th RECOMB Satellite Workshop on Comparative Genomics (RECOMB-CG'09), Sep 2009, Budapest, Hungary. pp.59-69. ⟨hal-00620365⟩

Share

Metrics

Record views

343

Files downloads

231