Highly scalable algorithms for robust string barcoding

B. DasGupta, K. M. Konwar, I. I. Mǎndoiu, A. A. Shvartsman

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations

Abstract

String barcoding is a recently introduced technique for genomic-based identification of microorganisms. In this paper we describe the engineering of highly scalable algorithms for robust string barcoding. Our methods enable distinguisher selection based on whole genomic sequences of hundreds of microorganisms of up to bacterial size on a well-equipped workstation, and can be easily parallelized to further extend the applicability range to thousands of bacterial size genomes. Experimental results on both randomly generated and NCBI genomic data show that whole-genome based selection results in a number of distinguishers nearly matching the information theoretic lower bounds for the problem.

Original languageEnglish (US)
Pages (from-to)1020-1028
Number of pages9
JournalLecture Notes in Computer Science
Volume3515
Issue numberII
DOIs
StatePublished - 2005
Externally publishedYes
Event5th International Conference on Computational Science - ICCS 2005 - Atlanta, GA, United States
Duration: May 22 2005May 25 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Highly scalable algorithms for robust string barcoding'. Together they form a unique fingerprint.

Cite this