News Archives

  • UNM
  • >Home
  • >News
  • >2006
  • >March
  • >A Formalization of the Use of Bounds with Applications in Biology and Engineering

A Formalization of the Use of Bounds with Applications in Biology and Engineering

March 7, 2006

  • Date: Tuesday, March 7th, 2006 
  • Time: 11:00 am — 12:15 pm
  • Place: Woodward 149

Sharlee Climer (UNM Faculty Candidate)
Doctoral Candidate Dept. of Computer Science and Engineering Dept. of Biology Washington University in St. Louis

In this presentation, we reflect on the history of the use of bounds and observe that previous research has focused on bounds derived from relaxations of constraints. However, bounds can be derived by tightening constraints, adding or deleting variables, or modifying the objective function. A formalization of the use of bounds as a two-step procedure, called limit crossing, is presented.

We used limit crossing to produce an original search strategy called cut-and-solve. We compared a simple, generic implementation of cut-and-solve with state-of-the-art solvers for seven real-world Traveling Salesman Problem classes. Cut-and-solve was faster when solving large instances for five of the problem classes and able to solve larger (sometimes substantially larger) instances for four classes.

We are currently using limit crossing for the biological problem of inferring haplotypes. A haplotype is a set of nucleotide sites gathered from a stretch of DNA. Genetic association studies use haplotypes to identify correlations between diseases and genes. We are implementing a limit-crossing tool for haplotype inferencing based on characteristics that can be expected from human populations.

Biography:

Sharlee Climer is a doctoral candidate at Washington University in St. Louis. Her advisors are Weixiong Zhang, in the department of Computer Science, and Alan Templeton, in the department of Biology. She holds degrees in Physics (BA), Civil/Structural Engineering (BS), and Computer Science (BS and MS). She is a computational scientist with a focus on combinatorial optimization problems. Sharlee has presented tutorials on her dissertation work at both the 19th International Joint Conference on Artificial Intelligence (IJCAI’05) and the 20th National Conference on Artificial Intelligence (AAAI’05). She has served on program committees for the 20th National Conference on Artificial Intelligence (AAAI’05) and the 2002, 2005, and 2006 Olin Conferences. Sharlee is the recipient of a National Defense Science and Engineering Graduate (NDSEG) Fellowship, an Olin Fellowship, and more than a dozen scholarships.