# DOTTED SUFFIX TREES: A STRUCTURE FOR APPROXIMATE TEXT INDEXING

**Luis Coelho**,

**Departamento de Engenharia Informática** –

## Abstract:

The problem we address is text indexing for approximate matching. We consider that we are given a text T which undergoes some preprocessing to generate an index. We can later query this index to identify the places where a string occurs up to a certain number of allowed errors k, where by error we mean the substitution, deletion or replacement of one character (edition or Levenstein distance).

We present a structure for indexing which occupies space O(n log^k n) in the average case, independent of alphabet size, n being the text size. This structure can be used to report the existence of a match with k errors in O (3k mk+1 ) and to report the occurrences in O(3^k m^{k+1} + ed) time, where m is the length of the pattern and where ed the number of matching edit scripts. These bounds are independent of alphabet size. The construction of the structure has time bound by O (k N |S|), where N is the number of nodes in the index and |S| the alphabet size.

Date: 2006-Jul-06 Time: 16:30:00 Room: 336

For more information:

### Upcoming Events

### Workshop “Metabolism and mathematical models: Two for a tango” – 2nd Edition

**Title: ** Workshop Metabolism and mathematical models: Two for a tango – 2nd Edition

**Dates:** October 25-26, 2022

**Location:** This workshop will be held in a virtual way

The topic of this workshop is metabolism in general, with a special focus, although not exclusive, on parasitology. Besides an exploration of the biological, biochemical and biomedical aspects, the workshop will also aim at presenting some of the mathematical modelling, algorithmic theory and software development that have become crucial to explore such aspects.

This workshop is being organised in the context of two projects, both with the Inria European Team Erable. One of the projects involves a partnership with the University of São Paulo (USP), in São Paulo, Brazil, more specifically the Institute of Mathematics and Statistics (IME) and the Institute of Biomedical Sciences – Inria Associated Team Capoeira – and the other involves the Inesc-ID/IST in Portugal, ETH in Zürich and EMBL in Heidelberg – H2020 Twinning Project Olissipo.

The workshop is open to all members of these two projects but also, importantly, to the community in general.

The program and more details are available here.