Approximate pattern matching on elastic-degenerate text

Giulia Bernardini; Nadia Pisanti; Solon P. Pissis; Giovanna Rosone

doi:10.1016/j.tcs.2019.08.012

Approximate pattern matching on elastic-degenerate text

Giulia Bernardini^*, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g., pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists a non-combinatorial O(nm^1.381+N)-time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O(k²mG+kN)-time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG+kN)-time and O(m)-space algorithm for solving the problem under Hamming distance.

Original language	English
Pages (from-to)	109-122
Number of pages	14
Journal	Theoretical Computer Science
Volume	812
DOIs	https://doi.org/10.1016/j.tcs.2019.08.012
Publication status	Published - 6 Apr 2020
Externally published	Yes

Funding

NP and GR are partially supported by the project MIUR -SIR CMACBioSeq (“Combinatorial methods for analysis and compression of biological sequences”) grant n. RBSI146R5L . GB, NP, and GR are partially supported by the project UniPi PRA_2017_44 (“Advanced computational methodologies for the analysis of biomedical data”). NP, SPP, and GR are partially supported by the Royal Society project IE 161274 (“Processing uncertain sequences: combinatorics and applications”).

Funders	Funder number
Royal Society	IE 161274
Ministero dell’Istruzione, dell’Università e della Ricerca	RBSI146R5L, UniPi PRA_2017_44

Keywords

Degenerate strings
Elastic-degenerate strings
Pan-genome
Pattern matching
Uncertain sequences

Access to Document

10.1016/j.tcs.2019.08.012

Persistent URL (handle)

Persistent link

Cite this

@article{722570d5529e4ced9811984a9b385540,

title = "Approximate pattern matching on elastic-degenerate text",

abstract = "An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g., pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists a non-combinatorial O(nm1.381+N)-time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O(k2mG+kN)-time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG+kN)-time and O(m)-space algorithm for solving the problem under Hamming distance.",

keywords = "Degenerate strings, Elastic-degenerate strings, Pan-genome, Pattern matching, Uncertain sequences",

author = "Giulia Bernardini and Nadia Pisanti and Pissis, {Solon P.} and Giovanna Rosone",

year = "2020",

month = apr,

day = "6",

doi = "10.1016/j.tcs.2019.08.012",

language = "English",

volume = "812",

pages = "109--122",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Approximate pattern matching on elastic-degenerate text

AU - Bernardini, Giulia

AU - Pisanti, Nadia

AU - Pissis, Solon P.

AU - Rosone, Giovanna

PY - 2020/4/6

Y1 - 2020/4/6

N2 - An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g., pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists a non-combinatorial O(nm1.381+N)-time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O(k2mG+kN)-time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG+kN)-time and O(m)-space algorithm for solving the problem under Hamming distance.

AB - An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g., pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists a non-combinatorial O(nm1.381+N)-time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O(k2mG+kN)-time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG+kN)-time and O(m)-space algorithm for solving the problem under Hamming distance.

KW - Degenerate strings

KW - Elastic-degenerate strings

KW - Pan-genome

KW - Pattern matching

KW - Uncertain sequences

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

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

U2 - 10.1016/j.tcs.2019.08.012

DO - 10.1016/j.tcs.2019.08.012

M3 - Article

AN - SCOPUS:85070355371

SN - 0304-3975

VL - 812

SP - 109

EP - 122

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Approximate pattern matching on elastic-degenerate text

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this