Related Experiment Videos
Incremental paradigms of motif discovery
Alberto Apostolico1, Laxmi Parida
1Dipartimento di Ingegneria dell' Informazione, Università di Padova, Padova, Italy. axa@cs.purdue.edu
Summary
This study introduces an efficient method for extracting maximal irredundant motifs from strings. A new algorithm achieves an O(n^3) time complexity for motif discovery.
Area of Science:
- Bioinformatics
- Computational Biology
- Stringology
Background:
- Identifying recurring patterns (motifs) in biological sequences is crucial for understanding genetic function.
- Existing methods for motif extraction can be computationally intensive.
- Maximal irredundant motifs offer a concise representation of sequence information.
Purpose of the Study:
- To develop an efficient algorithm for extracting maximal irredundant motifs from a given string.
- To establish a theoretical bound on the number of such motifs.
- To explore novel characterizations of motifs using partial order theory.
Main Methods:
- Combinatorial analysis to determine bounds on motif counts.
- Iterative updates of motif sets based on string extensions.
- Development of specialized data structures leveraging partial order properties.
- Implementation of an incremental discovery algorithm.
Main Results:
- A linear bound on the total number of maximal irredundant motifs was established.
- Novel characterizations of motifs based on partial orders were identified.
- An O(n^3) time complexity incremental algorithm for motif extraction was developed.
Conclusions:
- The proposed approach provides an efficient method for maximal irredundant motif extraction.
- The theoretical framework supports the design of optimized algorithms for motif discovery.
- This work contributes to advancing computational methods in bioinformatics and string analysis.