Skip to Main content Skip to Navigation
Journal articles

Finding Nested Common Intervals Efficiently

Abstract : In this paper, we study the problem of efficiently finding 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 cubic time algorithm for finding all nested common intervals. We reduce this complexity by providing a quadratic time algorithm computing an irredundant output. We then show, by providing a third algorithm, that finding only the maximal nested common intervals can be done in linear time. Finally, we prove that finding approximate nested common intervals is fixed parameter tractable. Considering sequences, we provide solutions (modifications of previously defined algorithms and a new algorithm) for different variants of the problem, depending on the treatment one wants to apply to duplicated genes. This includes a polynomial-time algorithm for a variant implying a matching of the genes in the cluster, a setting that for other problems often leads to hardness.
Document type :
Journal articles
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Monday, October 10, 2011 - 4:37:24 PM
Last modification on : Friday, September 16, 2022 - 1:52:51 PM


Files produced by the author(s)


  • HAL Id : hal-00619751, version 1


Guillaume Blin, David Célestin Faye, Jens Stoye. Finding Nested Common Intervals Efficiently. Journal of Computational Biology, Mary Ann Liebert, 2010, 17 (9), pp.1183-1194. ⟨hal-00619751⟩



Record views


Files downloads