Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

An O(n log n)-time algorithm for the restriction scaffold assignment problem.

Justin Colannino1, Mirela Damian, Ferran Hurtado

  • 1School of Computer Science, McGill University, Montréal, Québec Canada.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|June 10, 2006
PubMed
Summary

This study presents an efficient algorithm for the restriction scaffold assignment problem. The new method significantly improves computational time for finding minimum-cost solutions, especially for points on a line.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Identification of Perception Differences in Personality Factors and Autonomy by Sporting Age Category in Competitive Bodybuilders.

International journal of environmental research and public health·2023
See all related articles

Area of Science:

  • Computational geometry
  • Algorithm analysis
  • Data science

Background:

  • The restriction scaffold assignment problem involves mapping points from a larger set (S) to a smaller set (T).
  • Existing algorithms for this problem have a time complexity of O(n^2).

Purpose of the Study:

  • To develop a more efficient algorithm for the restriction scaffold assignment problem.
  • To reduce the time complexity for finding minimum-cost solutions.

Main Methods:

  • An algorithm is presented for the restriction scaffold assignment problem.
  • The algorithm's efficiency is analyzed under specific conditions.

Main Results:

  • The algorithm achieves O(n log n) time complexity for points on a line using the L(1) metric.

Related Experiment Videos

  • Linear time complexity is achieved if the point sets are presorted.

    • Conclusions:

    • The developed algorithm offers a significant improvement over previous methods.
    • This advancement enhances the efficiency of solving the restriction scaffold assignment problem.