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

Modeling Fluid Mixing in Microfluidic Grids This is an application to model fluid mixing in grid-based microfluidic chips. It provides a fast approximation of velocity and concentration at outlets for given grid-based chip designs. 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.


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. 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.

Faculty

Marek Chrobak
Marek Chrobak

Office: Bourns Hall A159C



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: WCH 336



My research has been focused on the design and analysis of algorithms of either theoretical or practical importance. Some of my past work includes approximation algorithms, average-case analysis, computational complexity, and computational learning. My current work is mostly concerned with algorithmic and machine learning problems in bioinformatics and biomedical informatics.


Stefano Lonardi

Office: WCH 325



Research interests: computational molecular biology, bioinformatics, design of algorithms, machine learning and data mining.


Yihan Sun

Office: TBD



Broad topics in the theory and practice of parallel computing, including algorithms, data structures, frameworks, implementations, and their applications. My work involves improving asymptotical theoretical bounds, simplifying algorithms and proofs, and developing efficient solutions to real-world problems.


Amey Bhangale

Office: TBD



My research interests lie in Complexity Theory. More specifically, I am interested in topics related to approximation algorithms, constraint satisfaction problems, analysis of Boolean functions and probabilistically checkable proofs.


Yan Gu

Office: TBD



My current research interest is design efficient (usually parallel) algorithms for large-scale data with good performance in practice.


Silas Richelson

Office: Bourns Hall A159



My research interests are in Cryptography, Computer Security and Complexity Theory.

Students and postdocs

Md. Abid Hasan
Ph.D. candidate, Computer Science

Abbas Roayaei
Ph.D. candidate, Computer Science

Qihua Liang
Ph.D. candidate, GGB

Dipankar Ranjan Baisya
Ph.D. candidate, Computer Science

Huong Luu
Ph.D. candidate, Computer Science

Hao Chen
Ph.D. candidate, Computer Science

Dipan Shaw
Ph.D. candidate, Computer Science

Jiaqi Hao
MS, Computer Science

Parker Newton
PhD candidate, Computer Science
Irem Ergun
Ph.D. student, Computer Science

Sourya Roy
Ph.D. candidate, Computer Science

Yugarshi Shashwat
Ph.D. student, Computer Science, Computer Science

Alumni

Miguel Coviello
Ph.D. Computer Science (2019)
Xin Zhang
Ph.D. Computer Science

Yu-Ting Huang
Ph.D. Computer Science

Weihua Pan
Ph.D. Computer Science (2019)
Hind Alhakami
Ph.D. Computer Science (2017)
Rachid Ounit
Ph.D. Computer Science (2017)
Wei-Bung Wang
Ph.D. Computer Science
Guanqun Shi
Ph.D. Computer Science
Yang Yang
Visiting researcher
Monik Khare
Ph.D. Computer Science
Arman Yousefi
Ph.D. student, Computer Science
Elena Harris
Ph.D. Computer Science (2010)
Christos Koufogiannakis
Ph.D. Computer Science (2009)

Vladimir Vacic
Ph.D. Computer Science (2008)
YongHui Wu
Ph.D. Computer Science (2008)
Serdar Bozdag
Ph.D. Computer Science (2008)
Zhaocheng Fan
Visiting researcher
Qi Fu
Ph.D. Computer Science (2007)
Zheng Fu
Ph.D. Computer Science (2007)
Lan Liu
Ph.D. Computer Science (2007)
Mathilde Hurand
Visiting researcher
Zheng Liu
Ph.D. Computer Science (2006)
Jie Zheng
Ph.D. Computer Science (2006)
Wojciech Jawor
Ph.D. Computer Science (2006)
Qiaofeng Yang
Ph.D. Bioinformatics (2006)
M.S. Computer Science (2006)
Chuhu Yang
Ph.D. Bioinformatics (2005)
Xin Chen
Postdoc (2005)
Haifeng Li
Ph.D. Computer Science (2005)
Petr Kolman
Postdoc (2004)
Jing Li
Ph.D. Computer Science (2004)
Andres Figeuroa
Ph.D. Computer Science (2004)

Ashraful Arefeen
Ph.D. Computer Science