NDLI: On the repetitive collection indexing problem

Content Provider	IEEE Xplore Digital Library
Author	Alatabbi, A. Barton, C. Iliopoulos, C.S.
Copyright Year	2012
Description	Author affiliation: Department of Informatics, King's College London, London WC2R 2LS, United Kingdom (Alatabbi, A.; Barton, C.; Iliopoulos, C.S.)
Abstract	In large data sets such as genomes from a single species, large sets of reads, and version control data it is often noted that each entry only differs from another by a very small number of variations. This leads to a large set of data with a great deal of redundancy and repetitiveness. Rapid development in DNA sequencing technologies has caused a drastic growth in the size of publicly available sequence databases with such data. DNA sequencing has become so fast and cost-effective that sequencing individual genomes will soon become a common task [9] making querying and storing such sets of data an important task. In this paper, we propose an indexing structure for highly repetitive collections of sequence data based on a multilevel g-gram model. In particular, the proposed algorithm accommodates variations that may occur in the target sequence with respect to the reference sequence. The paper is organized as follows. Section [1] and [2] introduce the basic concepts and go through the related literature. In Section [3] we present notions and facts. Details of the proposed data structure/algorithm will be given in Section [5] and [4], Section [6] discusses complexity analysis and Section [7] gives conclusions of future work.
Starting Page	682
Ending Page	687
File Size	723076
Page Count	6
File Format	PDF
ISBN	9781467327466
e-ISBN	9781467327473
e-ISBN	9781467327442
DOI	10.1109/BIBMW.2012.6470220
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-10-04
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Genomics Humans DNA Index Structure Relative Compression Genome Databases Entropy Indexes Arrays Data Compression
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in