On the Border Length Minimization Problem (BLMP) on a Square Array

Details On the Border Length Minimization Problem (BLMP) on a Square Array On the Border Length Minimization Problem (BLMP) on a Square Array

2010-03-15

arxiv.org/abs/1003.2839v2

Computer Science

Data Structures and Algorithms

Scientific paper

Protein/Peptide microarrays are rapidly gaining momentum in the diagnosis of cancer. High-density and highthroughput peptide arrays are being extensively used to detect tumor biomarkers, examine kinase activity, identify antibodies having low serum titers and locate antibody signatures. Improving the yield of microarray fabrication involves solving a hard combinatorial optimization problem called the Border Length Minimization Problem (BLMP). An important question that remained open for the past seven years is if the BLMP is tractable or not. We settle this open problem by proving that the BLMP is NP-hard. We also present a hierarchical refinement algorithm which can refine any heuristic solution for the BLMP problem. We also prove that the TSP+1-threading heuristic is an O(N)- approximation. The hierarchical refinement solver is available as an opensource code at http://launchpad.net/blm-solve.

Affiliated with

Also associated with

No associations

Rating

On the Border Length Minimization Problem (BLMP) on a Square Array does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Border Length Minimization Problem (BLMP) on a Square Array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Border Length Minimization Problem (BLMP) on a Square Array will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-213925