[1] R. Chikhi, S. Derrien, A. Noumsi, P. Quinton. Combining flash memory and FPGAs to efficiently implement a massively parallel algorithm for content-based image retrieval. International Journal of Electronics, Volume 95, Number 7, pp. 621-635(15) (2008)  [PDF]

 

 

Talks:

Space-efficient and exact de Bruijn graph representation based on a Bloom filter, WABI, 2012. [PDF]

Computational methods for de novo assembly of NGS data, Thesis slides, 2012. [PDF]

Localized genome assembly from reads to scaffolds: practical traversal of the paired string graph , WABI, 2011. [PDF]

de novo assembly tools, Monument, Mapsembler, IBL, Lille, 2011. [PDF]

Paired-end read length lower bounds for genome re-sequencing, ISCB Student Council Symposium, 2009. [PDF]

 

Reports:

R. Chikhi. Computational Methods for de novo Assembly of Next-Generation Genome
Sequencing Data. PhD Thesis, 2008-2012.  [PDF]

Summary:  We discuss computational methods (theoretical models and algorithms) to perform the reconstruction (de novo assembly) of DNA sequences produced by high-throughput sequencers. This thesis introduces the following contributions:

• quantification of the maximum theoretical genome coverage achievable by sequencing data (paired reads) (Chapter 2)
  
• a set of computational problems that are related to paired assembly (Chapter 3)
• two novel concepts for practical assembly: localized assembly and memory-efficient reads indexing (Chapter 4)
• implementation details of a de novo assembly software package, the Monument assembler (Chapter 5)
• an algorithm that reconstructs variants of a known sequence in Mapsembler (Chapter 6)

 

R. Chikhi. Study of Unentanglement in Quantum Computing. Manuscript, research internship at MIT, Spring 2008.  [PDF]

Summary: We investigate the conjecture that one cannot simulate QMA(2) protocols in QMA using a quantum operation called a disentangler. Our results show that, when exponential precision is required, this conjecture holds unless P = NP. Moreover, also in the exponential precision case, we show that one only needs a stronger hypothesis to prove the conjecture.

 

R.Chikhi. Protein surface descriptors for binding sites comparison and ligand prediction. Manuscript, research internship at Purdue University, Summer 2007. [PDF]

Summary:  We present a model for two dimensional ligand binding pockets representation and we apply it to pocket-pocket matching and binding ligand prediction.

 

 

---

Software:


Minia assembler

Whole genome de novo assembler with very low memory usage, described in [11].

DSK: http://minia.genouest.org/dsk

K-mer counting software, low-memory, low disk usage, supports large values of k, described in [13].

KisSplice: http://alcovna.genouest.org/kissplice/
 
Alternative splicing calling from 1, 2 or more NGS RNA-seq datasets, see reference [9].

Mapsembler: http://alcovna.genouest.org/mapsembler/

Targeted assembly on a desktop computer, see reference [10].

Monument: http://www.irisa.fr/symbiose/people/rchikhi/monument.html

Whole genome de novo assembler, described in [6] and [7] and [Phd Thesis].

Pocket-Surfer:  http://dragon.bio.purdue.edu/pocket-surfer/index.php

Protein ligand binding pocket type prediction using a database of known binding sites. See [3] for more details.

Paired reads repetitions: on github

Software package for computing the ratio of single and paired (as in paired NGS reads) exact repetitions within a genome. Useful for obtaining re-sequencing lower bounds inspired by [Whiteford 05]. See [2] and the corresponding talk for sample results and details.

de Bruijn graph construction: on github

Hash table-free implementation of the de Bruijn graph for a set of reads. Also includes a tool that computes the union of two de Bruijn graphs and the cartesian product of abundances, useful for construction a multi-dataset de Bruijn graph.