title: Border length minimization problem on a square array.
abstract: Protein/peptide microarrays are rapidly gaining momentum in the diagnosis of cancer. High-density and high-throughput 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 7 years is if the BLMP is tractable or not. We settle this open problem by proving that the BLMP is [Formula: see text]-hard. We also present a hierarchical refinement algorithm that can refine any heuristic solution for the BLMP and prove that the TSP+1-threading heuristic is an O(N)-approximation.
authors: Computer Science and Engineering Department, University of Connecticut , Storrs, CT.
authors: Vamsi
authors: V
authors: Kundeti
authors: Sanguthevar
authors: S
authors: Rajasekaran
authors: Hieu
authors: H
authors: Dinh
mesh_terms: D000465:Algorithms; D000818:Animals; D006801:Humans; D008962:Models, Theoretical; D009363:Neoplasm Proteins / Q000378:metabolism*; D009369:Neoplasms / Q000175:diagnosis* / Q000378:metabolism*; D040081:Protein Array Analysis / Q000379:methods*
chemical_list: D009363:Neoplasm Proteins
keywords: DNA self-assembly; algorithms; combinatorial optimization; genomics; machine learning