Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes.
Zhixiang ChenRichard H. FowlerBin FuBinhai ZhuPublished in: COCOON (2006)
Keyphrases
- lower bound
- phylogenetic analysis
- upper bound
- sequence alignment
- comparative genomics
- integrality gap
- polynomial approximation
- distance measure
- np hard
- branch and bound
- error bounds
- linear programming relaxation
- branch and bound algorithm
- approximation algorithms
- comparative analysis
- rna sequences
- euclidean distance
- protein coding regions
- min sum
- randomized algorithm
- objective function
- lower and upper bounds
- approximation guarantees
- sequence similarity
- constant factor
- quadratic assignment problem
- coding regions
- worst case
- vc dimension