ICS 2011
|
|
Welcome to ICS2011
Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 444-459, 978-7-302-24517-9
Tsinghua University Press
We consider the problem of arranging elements on a circle so as to approximately preserve specified pairwise distances. This problem is closely related to optimization problems found in genome assembly. The current methods for genome sequencing involve cutting the genome into many segments, sequencing each (short) segment, and then reassembling the segments to determine the original sequence. A useful paradigm has been using "mate pair" information, which, for a circular genome (e.g. bacterial genomes), generates information about the directed distance between non-adjacent pairs of segments in the final sequence. Specifically, given a set of equations of the form xv − yu ≡ duv (mod q), we study the objective of maximizing a linear payoff function that depends on how close the value xv − yu (mod q) is to duv. We apply the rounding procedure used by Goemans and Williamson for "complex" semidefinite programs. Our main tool is a simple geometric lemma that allows us to easily compute the expected distance on a circle between two elements whose positions have been computed using this rounding procedure. Preview: 
|
Copyright 2010-2011, Institute for Computer Science, Tsinghua University, All Rights Reserved.