A Algorithms and Computational Biology Lab

Research Topics:

Algorithm

We are interested in all aspects of the design and analysis of combinatorial algorithms. Ongoing research includes:

  • approximation algorithms,
  • on-line algorithms,
  • computational geometry,
  • graph drawing,
  • information retrieval,
  • average-case analysis of algorithms,
  • computational complexity.

We are especially interested in algorithmic problems arising in computational molecular biology, such as:

  • comparative genomics,
  • SNP's and haplotype inference,
  • genome-wide analysis of structures of gene families,
  • DNA microarray analysis,
  • genome-level gene dynamics.

Projects
Oligonucleotide fingerprinting of ribosomal RNA genes (OFRG) is a method that permits the identification of arrayed ribosomal RNA genes (rDNA) through a series of hybridizaition experiments using small DNA probes. It provides a cost effective means to extensively analyze microbial communities and should have application in medicine, biotechnology and ecosystem studies. This project is funded by NSF DBI. PRImer Selector (PRISE) is an interactive software package for PCR primer design. PRISE enables the design of sequence-specific / sequence-selective PCR primers. One important feature of PRISE is that it automates the task of placing primer-template mismatches at the 3' end of the primers - a property that is crucial for sequence selectivity / specificity.
OligoSpawn is an efficient software for selecting two types of oligos, namely unique and popular oligos, from large unigene databases. MSOAR is a high-throughput system for ortholog assignment on a genome scale.
Two Sample Logo is a procedure for discovery of statistically significant position-specific differences in residue compositions between two multiple sequence alignments, as well as for graphical representation of those differences. Composition Profiler is a web-based tool that automates detection of enrichment or depletion patterns of individual amino acids or groups of amino acids classified by several physico-chemical and structural properties.
FLowgram Alignment Tool (FLAT) is a method for probabilistic matching of small RNA flowgrams against the reference genome. LRTag is an efficient software tool for selecting a minimum set of TagSNPs across multiple populations via the linkage disequilibrium criteria.
MSTmap is a genetic mapping tool which constructs the initial genetic map from the minimum spanning tree (MST) of a graph. It is able to detect genotyping errors and can handle various mapping populations including DH, Hap, BC, and RIL. MergeMap is software tool for merging individual genetic linkage maps into a consensus map. When there are conflicts among the individual maps, MergeMap is able to produce a graph which highlights the possible problematic marker occurrences.
Graphlet kernel is a supervised learning framework for annotating functional residues in protein structures. Each residue is represented as a vector of counts of labeled non‐isomorphic subgraphs (called graphlets) in the protein contact graph, and a similarity measure between two vertices is expressed as the inner product of their respective count vectors. BRAT is an accurate and efficient tool for mapping short bisulfite-treated reads obtained from the Solexa-Illumina Genome Analyzer. BRAT supports single-end and pair-end short reads mapping and allows alignment of different length reads/mates.

Faculty
Marek Chrobak
Marek Chrobak

Office: Engineering II Room 406
Phone: (951) 827-3769

Design and analysis of algorithms; data structures; theory of computation; combinatorial optimization; computational geometry; automata theory; graph theory; on-line algorithms; graph drawing algorithms; algorithms in discrete tomography.
Tao Jiang

Office: Engineering II Room 336
Phone: (951) 827-2991

Design and analysis of algorithms, with emphasis on approximation algorithms and average-case analysis; computational molecular biology, with emphasis on comparative genomics, SNP's and haplotype inference, genome-wide analysis of structures of gene families. Applications of Kolmogorov complexity.

Neal Young

Office: Engineering II Room 423
Phone: (951) 827-7146

Approximation algorithms for combinatorial optimization; Lagrangian-relaxation; algorithms for networks and caching; dynamic optimization problems; fast algorithms for special classes of linear programs.
Stefano Lonardi

Office: Engineering II Room 317
Phone: (951) 827-2203

Design of algorithms for mining large datasets in molecular biology, in particular of data mining algorithms on bio-sequences and biological networks; also, data compression and information theory.

Students and postdocs

Seyed Hamid Mirebrahim
Ph.D. candidate, Computer Science
Rachid Ounit
Ph.D. candidate, Computer Science
Hind Alhakami
Ph.D. candidate, Computer Science

Weihua Pan
Ph.D. student, Computer Science
Md. Abid Hasan
Ph.D. student, Computer Science
Masruba Tasnim
Ph.D. student, Computer Science

Ei-Wen Yang
Ph.D. student, Computer Science
Ashraful Arefeen
Ph.D. student, Computer Science
Xin Zhang
Ph.D. student, Computer Science

Jonathan Deans
B.S., Bioinfomatics, UC Santa Cruz
Yu-Ting Huang
Ph.D. student, Computer Science

Alumni

Wei-Bung Wang
Ph.D. candidate, Computer Science
Microsoft, Seattle
Guanqun Shi
Ph.D. student, Computer Science
Storm8, San Francisco
Yang Yang
Visiting researcher
Shanghai Jiao Tong University, China


Monik Khare
Ph.D. Computer Science
YP, Glendale, CA
Arman Yousefi
Ph.D. student, Computer Science
University of California, Los Angeles, CA
Elena Harris
Ph.D. Computer Science (2010)
University of Southern California, Los Angeles, CA

Christos Koufogiannakis
Ph.D. Computer Science (2009)
Vladimir Vacic
Ph.D. Computer Science (2008)
Cold Spring Harbor Laboratory, Cold Spring Harbor, NY
YongHui Wu
Ph.D. Computer Science (2008)
Google, Mountain View, CA

Serdar Bozdag
Ph.D. Computer Science (2008)
National Cancer Institute, Bethesda, MD
Zhaocheng Fan
Visiting researcher
Tsinghua University, Beijing, China
Qi Fu
Ph.D. Computer Science (2007)
Google, Irvine, CA

Zheng Fu
Ph.D. Computer Science (2007)
Google, Mountain View, CA
Lan Liu
Ph.D. Computer Science (2007)
Google, Mountain View, CA
Mathilde Hurand
Visiting researcher
Ecole Polytechnique, Palaiseau, France

Zheng Liu
Ph.D. Computer Science (2006)
City of Hope National Medical Center, Duarte, CA
Jie Zheng
Ph.D. Computer Science (2006)
NCBI, Bethesda, MD
Wojciech Jawor
Ph.D. Computer Science (2006)
Shopzilla, Los Angeles, CA

Qiaofeng Yang
Ph.D. Bioinformatics (2006)
M.S. Computer Science (2006)
Stanford University, Stanford, CA
Chuhu Yang
Ph.D. Bioinformatics (2005)
EraGen Biosciences, Madison, WI
Xin Chen
Postdoc (2005)
Nanyang Technological University, Singapore

Haifeng Li
Ph.D. Computer Science (2005)
University of Southern California, Los Angeles, CA
Petr Kolman
Postdoc (2004)
Charles University, Prague, Czech Republic
Jing Li
Ph.D. Computer Science (2004)
Case Western Reserve University, Cleveland, OH

Andres Figeuroa
Ph.D. Computer Science (2004)
University of Texas - Pan American, Edinburg, TX