Searching and Indexing Genomic Databases via Kernelization

The rapid advance of DNA sequencing technologies has yielded databases of thousands of genomes. To search and index these databases effectively, it is important that we take advantage of the similarity between those genomes. Several authors have recently suggested searching or indexing only one refe...

Descripción completa

Detalles Bibliográficos
Autores principales: Gagie, Travis, Puglisi, Simon J.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Frontiers Media S.A. 2015
Materias:
Bioengineering and Biotechnology
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4321636/
https://www.ncbi.nlm.nih.gov/pubmed/25710001
http://dx.doi.org/10.3389/fbioe.2015.00012
Descripción
Sumario:The rapid advance of DNA sequencing technologies has yielded databases of thousands of genomes. To search and index these databases effectively, it is important that we take advantage of the similarity between those genomes. Several authors have recently suggested searching or indexing only one reference genome and the parts of the other genomes where they differ. In this paper, we survey the 20-year history of this idea and discuss its relation to kernelization in parameterized complexity.

Ejemplares similares