A new family of string classifiers based on local relatedness

Yasuto Higa; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/11893318_14

A new family of string classifiers based on local relatedness

Yasuto Higa, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

This paper introduces a new family of string classifiers based on local relatedness. We use three types of local relatedness measurements, namely, longest common substrings (LCStr's), longest common subsequences (LCSeq's), and window-accumulated longest common sub-sequences (wLCSeq's). We show that finding the optimal classier for given two sets of strings (the positive set and the negative set), is NP-hard for all of the above measurements. In order to achieve practically efficient algorithms for finding the best classifier, we investigate pruning heuristics and fast string matching techniques based on the properties of the local relatedness measurements.

Original language	English
Title of host publication	Discovery Science - 9th International Conference, DS 2006, Proceedings
Publisher	Springer Verlag
Pages	114-124
Number of pages	11
ISBN (Print)	3540464913, 9783540464914
DOIs	https://doi.org/10.1007/11893318_14
Publication status	Published - 2006
Event	9th International Conference on Discovery Science, DS 2006 - Barcelona, Spain Duration: Oct 7 2006 → Oct 10 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4265 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	9th International Conference on Discovery Science, DS 2006
Country/Territory	Spain
City	Barcelona
Period	10/7/06 → 10/10/06

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11893318_14

Cite this

Higa, Y., Inenaga, S., Bannai, H., & Takeda, M. (2006). A new family of string classifiers based on local relatedness. In Discovery Science - 9th International Conference, DS 2006, Proceedings (pp. 114-124). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4265 LNAI). Springer Verlag. https://doi.org/10.1007/11893318_14

A new family of string classifiers based on local relatedness. / Higa, Yasuto; Inenaga, Shunsuke; Bannai, Hideo et al.
Discovery Science - 9th International Conference, DS 2006, Proceedings. Springer Verlag, 2006. p. 114-124 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4265 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Higa, Y, Inenaga, S, Bannai, H & Takeda, M 2006, A new family of string classifiers based on local relatedness. in Discovery Science - 9th International Conference, DS 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4265 LNAI, Springer Verlag, pp. 114-124, 9th International Conference on Discovery Science, DS 2006, Barcelona, Spain, 10/7/06. https://doi.org/10.1007/11893318_14

Higa Y, Inenaga S, Bannai H, Takeda M. A new family of string classifiers based on local relatedness. In Discovery Science - 9th International Conference, DS 2006, Proceedings. Springer Verlag. 2006. p. 114-124. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11893318_14

@inproceedings{e050465321824445b596bea7fef10e00,

title = "A new family of string classifiers based on local relatedness",

abstract = "This paper introduces a new family of string classifiers based on local relatedness. We use three types of local relatedness measurements, namely, longest common substrings (LCStr's), longest common subsequences (LCSeq's), and window-accumulated longest common sub-sequences (wLCSeq's). We show that finding the optimal classier for given two sets of strings (the positive set and the negative set), is NP-hard for all of the above measurements. In order to achieve practically efficient algorithms for finding the best classifier, we investigate pruning heuristics and fast string matching techniques based on the properties of the local relatedness measurements.",

author = "Yasuto Higa and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

year = "2006",

doi = "10.1007/11893318_14",

language = "English",

isbn = "3540464913",

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

publisher = "Springer Verlag",

pages = "114--124",

booktitle = "Discovery Science - 9th International Conference, DS 2006, Proceedings",

address = "Germany",

note = "9th International Conference on Discovery Science, DS 2006 ; Conference date: 07-10-2006 Through 10-10-2006",

}

TY - GEN

T1 - A new family of string classifiers based on local relatedness

AU - Higa, Yasuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2006

Y1 - 2006

N2 - This paper introduces a new family of string classifiers based on local relatedness. We use three types of local relatedness measurements, namely, longest common substrings (LCStr's), longest common subsequences (LCSeq's), and window-accumulated longest common sub-sequences (wLCSeq's). We show that finding the optimal classier for given two sets of strings (the positive set and the negative set), is NP-hard for all of the above measurements. In order to achieve practically efficient algorithms for finding the best classifier, we investigate pruning heuristics and fast string matching techniques based on the properties of the local relatedness measurements.

AB - This paper introduces a new family of string classifiers based on local relatedness. We use three types of local relatedness measurements, namely, longest common substrings (LCStr's), longest common subsequences (LCSeq's), and window-accumulated longest common sub-sequences (wLCSeq's). We show that finding the optimal classier for given two sets of strings (the positive set and the negative set), is NP-hard for all of the above measurements. In order to achieve practically efficient algorithms for finding the best classifier, we investigate pruning heuristics and fast string matching techniques based on the properties of the local relatedness measurements.

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

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

U2 - 10.1007/11893318_14

DO - 10.1007/11893318_14

M3 - Conference contribution

AN - SCOPUS:33750744852

SN - 3540464913

SN - 9783540464914

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

SP - 114

EP - 124

BT - Discovery Science - 9th International Conference, DS 2006, Proceedings

PB - Springer Verlag

T2 - 9th International Conference on Discovery Science, DS 2006

Y2 - 7 October 2006 through 10 October 2006

ER -

A new family of string classifiers based on local relatedness

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this