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

Exact and approximation algorithms for DNA tag set design.

Ion I Măndoiu1, Dragoş Trincă

  • 1Computer Science and Engineering Department, University of Connecticut, Storrs, CT 06269-2155, USA. ion.mandoiu@uconn.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|May 19, 2006
PubMed
Summary
This summary is machine-generated.

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

<i>Special Issue:</i> 13th International Conference on Computational Advances in Bio and Medical Sciences.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same author

MHASS: Microbiome HiFi Amplicon Sequencing Simulator.

Bioinformatics (Oxford, England)·2025
Same author

First Mitogenome of the Critically Endangered Arabian Leopard (<i>Panthera pardus nimr</i>).

Animals : an open access journal from MDPI·2025
Same author

<i>Special Section:</i> 12th International Computational Advances in Bio and Medical Sciences (ICCABS 2023).

Journal of computational biology : a journal of computational molecular cell biology·2025
Same author

A frameshift-generated cancer neoepitope that controls tumor burden in prophylaxis as well as therapy.

Journal of immunology (Baltimore, Md. : 1950)·2025
Same author

Low-avidity T cells drive endogenous tumor immunity in mice and humans.

Nature immunology·2025

This study introduces novel algorithms for DNA array tag set design, improving efficiency and increasing tag numbers by over 40% using cycle packing and greedy algorithms.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Designing efficient tag sets is crucial for universal DNA arrays.
  • Previous methods for tag set design faced scalability and optimization challenges.

Purpose of the Study:

  • To develop new, scalable solution methods for DNA array tag set design.
  • To improve the number of tags that can be generated for DNA arrays.

Main Methods:

  • Formulating tag set design as integer linear programming problems.
  • Developing approximation schemes for packing linear programs for scalability.
  • Connecting tag design to vertex-disjoint directed cycle packing in graphs.
  • Employing a greedy cycle packing algorithm combined with alphabetic tree search.

Related Experiment Videos

Main Results:

  • Integer linear programming formulations are presented and solved for moderate-sized instances.
  • Scalable algorithms based on packing linear programs are proposed.
  • A novel connection to directed cycle packing is established, enhancing tag design.
  • The combined greedy and tree search strategy increased tag numbers by over 40%.

Conclusions:

  • New computational methods offer significant improvements in DNA array tag set design.
  • The developed algorithms are more scalable and yield a higher number of usable tags.
  • The findings advance the field of DNA array design and genomic data analysis.