Toward optimal disk layout of genome scale suffix trees

Vikas K. Garg

doi:10.1007/978-3-642-17298-4_80

Toward optimal disk layout of genome scale suffix trees

Ei julkaistu Aalto-yliopiston affiliaatiolla

IBM

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

Abstrakti

Suffix trees provide for efficient indexing of numerous sequence processing problems in biological databases. We address the pivotal issue of improving the search efficiency of disk-resident suffix trees by improving the storage layout from a statistical learning viewpoint. In particular, we make the following contributions: we (a) introduce the Q-Optimal Disk Layout(Q-OptDL) problem in the context of suffix trees and prove it to be NP-Hard, and (b) propose an algorithm for improving the layout of suffix trees that is guaranteed to perform asymptotically no worse than twice the optimal disk layout.

Alkuperäiskieli	Englanti
Otsikko	Simulated Evolution and Learning - 8th International Conference, SEAL 2010, Proceedings
Sivut	711-715
Sivumäärä	5
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-642-17298-4_80
Tila	Julkaistu - 2010
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	International Conference on Simulated Evolution and Learning - Kanpur, Intia Kesto: 1 jouluk. 2010 → 4 jouluk. 2010 Konferenssinumero: 8

Julkaisusarja

Nimi	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta	6457 LNCS
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Conference

Conference	International Conference on Simulated Evolution and Learning
Lyhennettä	SEAL
Maa/Alue	Intia
Kaupunki	Kanpur
Ajanjakso	01/12/2010 → 04/12/2010

Pääsy asiakirjaan

10.1007/978-3-642-17298-4_80

Muut tiedostot ja linkit

Link to publication in Scopus

Siteeraa tätä

Garg, V. K. (2010). Toward optimal disk layout of genome scale suffix trees. teoksessa Simulated Evolution and Learning - 8th International Conference, SEAL 2010, Proceedings (Sivut 711-715). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 6457 LNCS). https://doi.org/10.1007/978-3-642-17298-4_80

@inproceedings{67bc80cbc322435ca00a89cfd2e29c8c,

title = "Toward optimal disk layout of genome scale suffix trees",

abstract = "Suffix trees provide for efficient indexing of numerous sequence processing problems in biological databases. We address the pivotal issue of improving the search efficiency of disk-resident suffix trees by improving the storage layout from a statistical learning viewpoint. In particular, we make the following contributions: we (a) introduce the Q-Optimal Disk Layout(Q-OptDL) problem in the context of suffix trees and prove it to be NP-Hard, and (b) propose an algorithm for improving the layout of suffix trees that is guaranteed to perform asymptotically no worse than twice the optimal disk layout.",

keywords = "0/1 Knapsack, Statistical Learning, Suffix Trees",

author = "Garg, {Vikas K.}",

year = "2010",

doi = "10.1007/978-3-642-17298-4_80",

language = "English",

isbn = "3642172970",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "711--715",

booktitle = "Simulated Evolution and Learning - 8th International Conference, SEAL 2010, Proceedings",

note = "International Conference on Simulated Evolution and Learning, SEAL ; Conference date: 01-12-2010 Through 04-12-2010",

}

Garg, VK 2010, Toward optimal disk layout of genome scale suffix trees. julkaisussa Simulated Evolution and Learning - 8th International Conference, SEAL 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vuosikerta 6457 LNCS, Sivut 711-715, International Conference on Simulated Evolution and Learning, Kanpur, Intia, 01/12/2010. https://doi.org/10.1007/978-3-642-17298-4_80

Toward optimal disk layout of genome scale suffix trees. / Garg, Vikas K.
Simulated Evolution and Learning - 8th International Conference, SEAL 2010, Proceedings. 2010. s. 711-715 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 6457 LNCS).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

TY - GEN

T1 - Toward optimal disk layout of genome scale suffix trees

AU - Garg, Vikas K.

N1 - Conference code: 8

PY - 2010

Y1 - 2010

N2 - Suffix trees provide for efficient indexing of numerous sequence processing problems in biological databases. We address the pivotal issue of improving the search efficiency of disk-resident suffix trees by improving the storage layout from a statistical learning viewpoint. In particular, we make the following contributions: we (a) introduce the Q-Optimal Disk Layout(Q-OptDL) problem in the context of suffix trees and prove it to be NP-Hard, and (b) propose an algorithm for improving the layout of suffix trees that is guaranteed to perform asymptotically no worse than twice the optimal disk layout.

AB - Suffix trees provide for efficient indexing of numerous sequence processing problems in biological databases. We address the pivotal issue of improving the search efficiency of disk-resident suffix trees by improving the storage layout from a statistical learning viewpoint. In particular, we make the following contributions: we (a) introduce the Q-Optimal Disk Layout(Q-OptDL) problem in the context of suffix trees and prove it to be NP-Hard, and (b) propose an algorithm for improving the layout of suffix trees that is guaranteed to perform asymptotically no worse than twice the optimal disk layout.

KW - 0/1 Knapsack

KW - Statistical Learning

KW - Suffix Trees

UR - http://www.scopus.com/inward/record.url?scp=78650724082&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17298-4_80

DO - 10.1007/978-3-642-17298-4_80

M3 - Conference article in proceedings

AN - SCOPUS:78650724082

SN - 3642172970

SN - 9783642172977

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 711

EP - 715

BT - Simulated Evolution and Learning - 8th International Conference, SEAL 2010, Proceedings

T2 - International Conference on Simulated Evolution and Learning

Y2 - 1 December 2010 through 4 December 2010

ER -

Toward optimal disk layout of genome scale suffix trees

Abstrakti

Julkaisusarja

Conference

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä