Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T21:18:13.206Z Has data issue: false hasContentIssue false

Forbidden Factors and Fragment Assembly

Published online by Cambridge University Press:  15 July 2002

F. Mignosi
Affiliation:
University of Palermo, Dipartimento di Matematica ed Applicazioni, Via Archirafi 34, 90123 Palermo, Italy; (mignosi@math.unipa.it)
A. Restivo
Affiliation:
University of Palermo, Dipartimento di Matematica ed Applicazioni, Via Archirafi 34, 90123 Palermo, Italy; (restivo@math.unipa.it)
M. Sciortino
Affiliation:
University of Palermo, Dipartimento di Matematica ed Applicazioni, Via Archirafi 34, 90123 Palermo, Italy; (mari@math.unipa.it)
Get access

Abstract

In this paper methods and results related to the notion of minimalforbidden words are applied to the fragment assembly problem. Thefragment assembly problem can be formulated, in its simplest form,as follows: reconstruct a word w from a given set I ofsubstrings (fragments) of a word w. We introduce anhypothesis involving the set of fragments I and the maximallength m(w) of the minimal forbidden factors of w. Suchhypothesis allows us to reconstruct uniquely the word w from theset I in linear time. We prove also that, if w is a wordrandomly generated by a memoryless source with identical symbolprobabilities, m(w) is logarithmic with respect to the size ofw. This result shows that our reconstruction algorithm is suitedto approach the above problem in several practical applicationse.g. in the case of DNA sequences.

Information

Type
Research Article
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable