Curtin University Homepage
  • Library
  • Help
    • Admin

    espace - Curtin’s institutional repository

    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item

    Fast, Practical Algorithms for Computing All the Repeats in a String

    154600_154600.pdf (238.7Kb)
    Access Status
    Open access
    Authors
    Puglisi, Simon
    Smyth, William
    Yusufu, M.
    Date
    2010
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Puglisi, Simon J. and Smyth, W.F. and Yusufu, Munina. 2010. Fast, Practical Algorithms for Computing All the Repeats in a String. Mathematics in Computer Science. 3 (4): pp. 373-389.
    Source Title
    Mathematics in Computer Science
    DOI
    10.1007/s11786-010-0033-6
    ISSN
    16618270
    School
    Digital Ecosystems and Business Intelligence Institute (DEBII)
    Remarks

    The original publication is available at http://www.springerlink.com

    URI
    http://hdl.handle.net/20.500.11937/36774
    Collection
    • Curtin Research Publications
    Abstract

    Given a string x = x[1..n] on an alphabet of size α, and a threshold p min ≥ 1, we describe four variants of an algorithm PSY1 that, using a suffix array, computes all the complete nonextendible repeats in x of length p ≥ p min . The basic algorithm PSY1–1 and its simple extension PSY1–2 are fast on strings that occur in biological, natural language and other applications (not highly periodic strings), while PSY1–3 guarantees Θ(n) worst-case execution time. The final variant, PSY1–4, also achieves Θ(n) processing time and, over the complete range of strings tested, is the fastest of the four. The space requirement of all four algorithms is about 5n bytes, but all make use of the “longest common prefix” (LCP) array, whose construction requires about 6n bytes. The four algorithms are faster in applications and use less space than a recently-proposed algorithm (Narisawa in Proceedings of 18th Annual Symposium on Combinatorial Pattern Matching, pp. 340–351, 2007) that produces equivalent output. The suffix array is not explicitly used by algorithms PSY1, but may be required for postprocessing; in this case, storage requirements rise to 9n bytes. We also describe two variants of a fast Θ(n)-time algorithm PSY2 for computing all complete supernonextendible repeats in x.

    Related items

    Showing items related by title, author, creator and subject.

    • Sorting suffixes of two-pattern strings
      Franek, F.; Smyth, Bill (2004)
      Recently, several authors presented linear recursive algorithms for sorting suffixes of a string. All these algorithms employ a similar three-step approach, based on an initial division of the suffixes of x into two sets: ...
    • Faster algorithms for computing maximal multirepeats in multiple sequences
      Iliopoulos, Costas; Smyth, Bill; Yusufu, M. (2009)
      A repeat in a string is a substring that occurs more than once. A repeat is extendible if every occurrence of the repeat has an identical letter either on the left or on the right; otherwise, it is maximal. A multirepeat ...
    • Fast optimal algorithms for computing all the repeats in a string
      Puglisi, Simon; Smyth, Bill; Yusufu, M. (2008)
      Given a string x = x[1..n] on an alphabet of size a, and a threshold pmin = 1, we first describe a new algorithm PSY1 that, based on suffix array construction, computes all the complete nonextendible repeats in x of length ...
    Advanced search

    Browse

    Communities & CollectionsIssue DateAuthorTitleSubjectDocument TypeThis CollectionIssue DateAuthorTitleSubjectDocument Type

    My Account

    Admin

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Follow Curtin

    • 
    • 
    • 
    • 
    • 

    CRICOS Provider Code: 00301JABN: 99 143 842 569TEQSA: PRV12158

    Copyright | Disclaimer | Privacy statement | Accessibility

    Curtin would like to pay respect to the Aboriginal and Torres Strait Islander members of our community by acknowledging the traditional owners of the land on which the Perth campus is located, the Whadjuk people of the Nyungar Nation; and on our Kalgoorlie campus, the Wongutha people of the North-Eastern Goldfields.