### Abstract

Let S and T be two finite sets of points on the real line with |S|+|T|=n and |S|>|T|. The restriction scaffold assignment problem in computational biology assigns each point of S to a point of T such that the sum of all the assignment costs is minimized, with the constraint that every element of T must be assigned at least one element of S. The cost of assigning an element si of S to an element tj of T is |s_{i} - t_{j}|, i.e., the distance between si and tj. In 2003 Ben-Dor, Karp, Schwikowski and Shamir [J. Comput. Biol. 10 (2) (2003) 385] published an O(nlogn) time algorithm for this problem. Here we provide a counterexample to their algorithm and present a new algorithm that runs in O(n2) time, improving the best previous complexity of O(n3).

Original language | English (US) |
---|---|

Pages (from-to) | 466-471 |

Number of pages | 6 |

Journal | Information Processing Letters |

Volume | 95 |

Issue number | 4 |

DOIs | |

State | Published - Aug 31 2005 |

### Fingerprint

### Keywords

- Analysis of algorithms
- Assignment problems
- Computational biology
- Computational geometry
- Information retrieval
- Operations research
- Rhythmic similarity measures

### ASJC Scopus subject areas

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications