Vicky Choi Assistant Professor Department of Computer Science Virginia Tech Office: KnowledgeworkII 222 Phone: (540) 231-2919; Fax: (540) 231-6075 Email: vchoi@(virginia tech's email address)

Research Interest:

Design, analysis and implementation of algorithms in bioinformatics, computational biology, computational chemistry, computational geometry, and discrete mathematics.

Teaching:

• I'm on leave till January 2009.
• Fall 2006: CS5124 Algorithms in Bioinformatics
• Spring 2006: CS5984 Algorithms in Structural Bioinformatics
• Fall 2005: CS5114 Theory of Algorithms
• Spring 2005: CS6104 Algorithms in Structural Bioinformatics
• Fall 2004: CS4104 Data and Algorithm Analysis

Current Research Projects:

Microarray Data Analysis using Galois (Concept) Lattice:

• Faster Algorithms for Constructing a Galois/Concept Lattice. Presented at SIAM Conference on Discrete Mathematics 2006, University of Victoria, Canada. [(pdf)](arXiv:cs.DM/0602069)
• Microarray Data Analysis (with Reinhard Laubenbacher, Karen Duca, Vy Lam and Yang Huang) [(pdf)]. Presented at DIMACS Workshop on Clustering Problems in Biological Networks, Piscataway, NJ, May 9--11, 2006. To appear at APBC 2007.

Point Pattern Matching:

• V. Choi, N. Goyal. An Efficient Approximation Algorithm for Point Pattern Matching Under Noise. The 7th International Symposium, Latin American Theoretical Informatics (LATIN 2006)}. Valdivia, Chile, March 19--24, 2006. Lecture Notes in Computer Science, Vol. 3887, 2006, pp 298--310. [Full version(pdf)]
• An Algorithmic Approach to the Identification of Rigid Domains in Proteins. [(pdf)] (Accepted to the special issue of Algorithmica)
• Applications: Protein Domain Motions Analysis; Flexible Protein Alignment (with Dave Bevan)

Protein Small-Molecule Docking and Conformation Analysis:

• V. Choi. Yucca: An efficient algorithm for small molecule docking. Chemistry and Biodiversity, Issue 11, 2005, pp1517 -- 1524. [preprint(pdf)] Presented at the Symposium on Computational Methods in Drug Design, Switzerland, 2005. [presentation(ppt)]
• V. Choi. On Updating Torsion Angles of Molecular Conformations. DIMACS Workshop on Information Processing by Protein Structures in Molecular Recognition, June 13-14 2005. Journal of Chemical Information and Modeling (formerly JCICS) 46 (1), 2006, pp438 -- 444. [preprint(pdf)] [presentation(ppt)]

Previous Work:

Protein-Protein Docking

• V. Choi, P.K. Agarwal, H. Edelsbrunner, J. Rudolph. Local Search Heuristic for Rigid Protein Docking. The 4th Workshop on Algorithms in Bioinformatics (WABI 2004), Lecture Notes in Computer Science, vol 3240, 2004, pp. 218--229.. [preprint(pdf)]
• V. Choi, N. Goyal. A Combinatorial Shape Matching Algorithm for Rigid Protein Docking. The Fifteenth Annual Symposium on Combinatorial Pattern Matching (CPM 2004), LNCS 3109, pp285-296, 2004.[preprint(pdf)]
• S. Bespamaytnikh, V. Choi, H. Edelsbrunner, J. Rudolph. Accurate Bound Protein Docking by Shape Complementarity Alone. Technical Report, Department of Computer Science, Duke University, 2003.

Sequence Assembly of the Human Genome

• BARNACLE's assembly of December 2001 freeze of the human genome
• The Sequence and Assembly of Highly Duplicated Regions in the Human Genome. Genome Sequencing & Biology meeting at Cold Spring Harbor Laboratory 2002.  [ppt]
• V. Choi, M. Farach-Colton. Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole Genomes. Gene,  320, 165-176, 2003.[reprint]
• PhD Thesis