## Abstract

The restriction scaffold assignment problem takes as input two finite point sets S and T (with S containing more points than T) and establishes a correspondence between points in S and points in T, such that each point in S maps to exactly one point in T and each point in T maps to at least one point in S. An algorithm is presented that finds a minimum-cost solution for this problem in O(n log n) time, provided that the points in S and T are restricted to lie on a line and the cost function δ is the L_{1} metric. This algorithm runs in linear time, if S and T are presorted. This improves the previously best-known O(n^{2})-time algorithm for this problem.

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

Pages (from-to) | 979-989 |

Number of pages | 11 |

Journal | Journal of Computational Biology |

Volume | 13 |

Issue number | 4 |

DOIs | |

State | Published - May 2006 |

## Keywords

- Algorithm
- Assignment
- Linear
- Matching
- Minimum cost
- Restricted scaffold

## ASJC Scopus subject areas

- Modeling and Simulation
- Molecular Biology
- Genetics
- Computational Mathematics
- Computational Theory and Mathematics