Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | 박희진 | - |
dc.date.accessioned | 2018-03-26T01:43:39Z | - |
dc.date.available | 2018-03-26T01:43:39Z | - |
dc.date.issued | 2013-07 | - |
dc.identifier.citation | Lecture Notes in Computer Science, 2013, 8288, P.337-348 | en_US |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | https://link.springer.com/chapter/10.1007%2F978-3-642-45278-9_29 | - |
dc.identifier.uri | http://hdl.handle.net/20.500.11754/52109 | - |
dc.description.abstract | We consider an index data structure for similar strings. The generalized suffix tree can be a solution for this. The generalized suffix tree of two strings A and B is a compacted trie representing all suffixes in A and B. It has |A|?+?|B| leaves and can be constructed in O(|A|?+?|B|) time. However, if the two strings are similar, the generalized suffix tree is not efficient because it does not exploit the similarity which is usually represented as an alignment of A and B.In this paper we propose a space/time-efficient suffix tree of alignment which wisely exploits the similarity in an alignment. Our suffix tree for an alignment of A and B has |A|?+?l d ?+?l 1 leaves where l d is the sum of the lengths of all parts of B different from A and l 1 is the sum of the lengths of some common parts of A and B. We did not compromise the pattern search to reduce the space. Our suffix tree can be searched for a pattern P in O(|P|?+?occ) time where occ is the number of occurrences of P in A and B. We also present an efficient algorithm to construct the suffix tree of alignment. When the suffix tree is constructed from scratch, the algorithm requires O(|A|?+?l d ?+?l 1?+?l 2) time where l 2 is the sum of the lengths of other common substrings of A and B. When the suffix tree of A is already given, it requires O(l d ?+?l 1?+?l 2) time. | en_US |
dc.language.iso | en | en_US |
dc.publisher | SPRINGER-VERLAG | en_US |
dc.subject | Indexes for similar data | en_US |
dc.subject | suffix trees | en_US |
dc.subject | alignments | en_US |
dc.title | Suffix Tree of Alignment: An Efficient Index for Similar Data. | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.1007/978-3-642-45278-9_29 | - |
dc.relation.page | 337-348 | - |
dc.contributor.googleauthor | Na, Joong Chae | - |
dc.contributor.googleauthor | Park, Heejin | - |
dc.contributor.googleauthor | Crochemore, Maxime | - |
dc.contributor.googleauthor | Holub, Jan | - |
dc.contributor.googleauthor | Iliopoulos, Costas S. | - |
dc.contributor.googleauthor | Mouchard, Laurent | - |
dc.contributor.googleauthor | Park, Kunsoo | - |
dc.relation.code | 20130050 | - |
dc.sector.campus | S | - |
dc.sector.daehak | COLLEGE OF ENGINEERING[S] | - |
dc.sector.department | DEPARTMENT OF COMPUTER SCIENCE | - |
dc.identifier.pid | hjpark | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.