62 0

Full metadata record

DC FieldValueLanguage
dc.contributor.author박희진-
dc.date.accessioned2018-03-24T01:34:53Z-
dc.date.available2018-03-24T01:34:53Z-
dc.date.issued2013-10-
dc.identifier.citationString Processing & Information Retrieval, 2013, 8214, P.243-254en_US
dc.identifier.isbn978-3-319-02431-8-
dc.identifier.isbn978-3-319-02432-5-
dc.identifier.issn1611-3349-
dc.identifier.issn0302-9743-
dc.identifier.urihttps://link.springer.com/chapter/10.1007/978-3-319-02432-5_27-
dc.identifier.urihttp://hdl.handle.net/20.500.11754/51709-
dc.description.abstractThe suffix tree of alignment is an index data structure for similar strings. Given an alignment of similar strings, it stores all suffixes of the alignment, called alignment-suffixes. An alignment-suffix represents one suffix of a string or suffixes of multiple strings starting at the same position in the alignment. The suffix tree of alignment makes good use of similarity in strings theoretically. However, suffix trees are not widely used in biological applications because of their huge space requirements, and instead suffix arrays are used in practice. In this paper we propose a space-economical version of the suffix tree of alignment, named the suffix array of alignment (SAA). Given an alignment ρ of similar strings, the SAA for ρ is a lexicographically sorted list of all the alignment-suffixes of ρ. The SAA supports pattern search as efficiently as the generalized suffix array. Our experiments show that our index uses only 14% of the space used by the generalized suffix array to index 11 human genome sequences. The space efficiency of our index increases as the number of the genome sequences increases. We also present an efficient algorithm for constructing the SAA. ⓒ Springer International Publishing 2013.en_US
dc.description.sponsorshipJoong Chae Na was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education, Science and Technology(2012-0003214), and by the IT R&D program of MKE/KEIT [10038768, The Development of Supercomputing System for the Genome Analysis]. Heejin Park was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education, Science and Technology(2012-0006999), by Seoul Creative Human Development Program (HM120006), by the Proteogenomics Research Program through the National Research Foundation of Korea funded by the Korean Ministry of Education, Science and Technology, and by the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT & Future Planning(2012-054452). Laurent Mouchard was supported by theFrench Ministry of Foreign Affairs Grant 27828RG (INDIGEN, PHC STAR 2012). Kunsoo Park was supported by National Research Foundation of Korea Grant funded by the Korean Government(MSIP) (2012K1A3A4A07030483), and by Next-Generation Information Computing Development Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Science, ICT & Future Planning (2011-0029924).en_US
dc.language.isoenen_US
dc.publisherSpringer-Verlag Berlin Heidelberg 2013en_US
dc.subjectIndexes for similar dataen_US
dc.subjectsuffix arraysen_US
dc.subjectalignmentsen_US
dc.titleSuffix Array of Alignment: A Practical Index for Similar Data.en_US
dc.typeArticleen_US
dc.identifier.doi10.1007/978-3-319-02432-5_33-
dc.relation.page243-254-
dc.contributor.googleauthorNa, Joong Chae-
dc.contributor.googleauthorPark, Heejin-
dc.contributor.googleauthorLee, Sunho-
dc.contributor.googleauthorHong, Minsung-
dc.contributor.googleauthorLecroq, Thierry-
dc.contributor.googleauthorMouchard, Laurent-
dc.contributor.googleauthorPark, Kunsoo-
dc.relation.code20130089-
dc.sector.campusS-
dc.sector.daehakCOLLEGE OF ENGINEERING[S]-
dc.sector.departmentDEPARTMENT OF COMPUTER SCIENCE-
dc.identifier.pidhjpark-
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE