Skip to content
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Publication Details
AFRICAN RESEARCH NEXUS
SHINING A SPOTLIGHT ON AFRICAN RESEARCH
biochemistry, genetics and molecular biology
Finding nested common intervals efficiently
Journal of Computational Biology, Volume 17, No. 9, Year 2010
Notification
URL copied to clipboard!
Description
In this article, 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. © Copyright 2010, Mary Ann Liebert, Inc.
Authors & Co-Authors
Blin, Guillaume
France, Marne-la-vallee
Laboratoire D’informatique Gaspard-monge
Faye, David
France, Marne-la-vallee
Laboratoire D’informatique Gaspard-monge
Senegal, Saint-louis
Université Gaston Berger de Saint-louis
Stoye, Jens
Germany, Bielefeld
Universität Bielefeld
Statistics
Citations: 3
Authors: 3
Affiliations: 3
Identifiers
Doi:
10.1089/cmb.2010.0089
ISSN:
10665277
Research Areas
Genetics And Genomics
Study Design
Case-Control Study