A linear-space algorithm for the substring constrained alignment problem

Yoshifumi Sakai

doi:10.1007/978-3-319-46049-9_2

A linear-space algorithm for the substring constrained alignment problem

Yoshifumi Sakai

AGR - Agricultural Bioscience

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

Abstract

In a string similarity metric adopting affine gap penalties, we propose a quadratic-time, linear-space algorithm for the following constrained string alignment problem. The input of the problem is a pair of strings to be aligned and a pattern given as a string. Let an occurrence of the pattern in a string be a minimal substring of the string that is most similar to the pattern. Then, the output of the problem is a highestscoring alignment of the pair of strings that matches an occurrence of the pattern in one string and an occurrence of the pattern in the other, where the score of the alignment excludes the similarity between the matched occurrences of the pattern. This problem may arise when we know that each of the strings has exactly one meaningful occurrence of the pattern and want to determine a putative pair of such occurrences based on homology of the strings.

Original language	English
Title of host publication	String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings
Editors	Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
Publisher	Springer Verlag
Pages	15-21
Number of pages	7
ISBN (Print)	9783319460482
DOIs	https://doi.org/10.1007/978-3-319-46049-9_2
Publication status	Published - 2016
Event	23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 - Beppu, Japan Duration: 2016 Oct 18 → 2016 Oct 20

Publication series

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

Conference

Conference	23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016
Country/Territory	Japan
City	Beppu
Period	16/10/18 → 16/10/20

Access to Document

10.1007/978-3-319-46049-9_2

Cite this

Sakai, Y. (2016). A linear-space algorithm for the substring constrained alignment problem. In S. Inenaga, K. Sadakane, & T. Sakai (Eds.), String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings (pp. 15-21). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9954 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-46049-9_2

Sakai, Yoshifumi. / A linear-space algorithm for the substring constrained alignment problem. String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. editor / Shunsuke Inenaga ; Kunihiko Sadakane ; Tetsuya Sakai. Springer Verlag, 2016. pp. 15-21 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e5f165b536d442a7ae652b6c6431bec6,

title = "A linear-space algorithm for the substring constrained alignment problem",

abstract = "In a string similarity metric adopting affine gap penalties, we propose a quadratic-time, linear-space algorithm for the following constrained string alignment problem. The input of the problem is a pair of strings to be aligned and a pattern given as a string. Let an occurrence of the pattern in a string be a minimal substring of the string that is most similar to the pattern. Then, the output of the problem is a highestscoring alignment of the pair of strings that matches an occurrence of the pattern in one string and an occurrence of the pattern in the other, where the score of the alignment excludes the similarity between the matched occurrences of the pattern. This problem may arise when we know that each of the strings has exactly one meaningful occurrence of the pattern and want to determine a putative pair of such occurrences based on homology of the strings.",

author = "Yoshifumi Sakai",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 ; Conference date: 18-10-2016 Through 20-10-2016",

year = "2016",

doi = "10.1007/978-3-319-46049-9_2",

language = "English",

isbn = "9783319460482",

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

publisher = "Springer Verlag",

pages = "15--21",

editor = "Shunsuke Inenaga and Kunihiko Sadakane and Tetsuya Sakai",

booktitle = "String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings",

address = "Germany",

}

Sakai, Y 2016, A linear-space algorithm for the substring constrained alignment problem. in S Inenaga, K Sadakane & T Sakai (eds), String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9954 LNCS, Springer Verlag, pp. 15-21, 23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016, Beppu, Japan, 16/10/18. https://doi.org/10.1007/978-3-319-46049-9_2

A linear-space algorithm for the substring constrained alignment problem. / Sakai, Yoshifumi.
String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. ed. / Shunsuke Inenaga; Kunihiko Sadakane; Tetsuya Sakai. Springer Verlag, 2016. p. 15-21 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9954 LNCS).

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

TY - GEN

T1 - A linear-space algorithm for the substring constrained alignment problem

AU - Sakai, Yoshifumi

N1 - Publisher Copyright: © Springer International Publishing AG 2016.

PY - 2016

Y1 - 2016

N2 - In a string similarity metric adopting affine gap penalties, we propose a quadratic-time, linear-space algorithm for the following constrained string alignment problem. The input of the problem is a pair of strings to be aligned and a pattern given as a string. Let an occurrence of the pattern in a string be a minimal substring of the string that is most similar to the pattern. Then, the output of the problem is a highestscoring alignment of the pair of strings that matches an occurrence of the pattern in one string and an occurrence of the pattern in the other, where the score of the alignment excludes the similarity between the matched occurrences of the pattern. This problem may arise when we know that each of the strings has exactly one meaningful occurrence of the pattern and want to determine a putative pair of such occurrences based on homology of the strings.

AB - In a string similarity metric adopting affine gap penalties, we propose a quadratic-time, linear-space algorithm for the following constrained string alignment problem. The input of the problem is a pair of strings to be aligned and a pattern given as a string. Let an occurrence of the pattern in a string be a minimal substring of the string that is most similar to the pattern. Then, the output of the problem is a highestscoring alignment of the pair of strings that matches an occurrence of the pattern in one string and an occurrence of the pattern in the other, where the score of the alignment excludes the similarity between the matched occurrences of the pattern. This problem may arise when we know that each of the strings has exactly one meaningful occurrence of the pattern and want to determine a putative pair of such occurrences based on homology of the strings.

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

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

U2 - 10.1007/978-3-319-46049-9_2

DO - 10.1007/978-3-319-46049-9_2

M3 - Conference contribution

AN - SCOPUS:84989870180

SN - 9783319460482

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

SP - 15

EP - 21

BT - String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings

A2 - Inenaga, Shunsuke

A2 - Sadakane, Kunihiko

A2 - Sakai, Tetsuya

PB - Springer Verlag

T2 - 23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016

Y2 - 18 October 2016 through 20 October 2016

ER -

Sakai Y. A linear-space algorithm for the substring constrained alignment problem. In Inenaga S, Sadakane K, Sakai T, editors, String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. Springer Verlag. 2016. p. 15-21. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-46049-9_2

A linear-space algorithm for the substring constrained alignment problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this