6533b86dfe1ef96bd12ca0dd
RESEARCH PRODUCT
Longest Motifs with a Functionally Equivalent Central Block
Maxime CrochemoreMaxime CrochemoreMarie-france SagotRaffaele Giancarlosubject
Discrete mathematics0303 health sciences[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Block (permutation group theory)0102 computer and information sciences01 natural sciencesCombinatoricsKleene algebra03 medical and health sciencesClosure (mathematics)010201 computation theory & mathematicsAlgorithmicsKleene starRegular expressionTime complexity030304 developmental biologyMathematicsComplement (set theory)description
International audience; This paper presents a generalization of the notion of longest repeats with a block of k don't care symbols introduced by [Crochemore et al., LATIN 2004] (for k fixed) to longest motifs composed of three parts: a first and last that parameterize match (that is, match via some symbol renaming, initially unknown), and a functionally equivalent central block. Such three-part motifs are called longest block motifs. Different types of functional equivalence, and thus of matching criteria for the central block are considered, which include as a subcase the one treated in [Crochemore et al., LATIN 2004] and extend to the case of regular expressions with no Kleene closure or complement operation. We show that a single general algorithmic tool that is a non-trivial extension of the ideas introduced in [Crochemore et al., LATIN 2004] can handle all the various kinds of longest block motifs defined in this paper. The algorithm complexity is, in all cases, in O(n log n).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2004-10-05 |