• DocumentCode
    3209544
  • Title

    A natural number based linear time filtering approach to finding all occurrences of a DNA pattern

  • Author

    Vu Quang Le

  • Author_Institution
    Muroran Inst. of Technol., Hokkaido
  • fYear
    2006
  • fDate
    Oct. 15 2006-Dec. 18 2006
  • Firstpage
    134
  • Lastpage
    137
  • Abstract
    String matching and searching techniques have been extensively studied in different research works. They currently play an essential part in the field of computational biology. Most of those techniques, from classics to their improved versions could successfully accomplish the task in linear time. In this paper, I propose a new searching approach based on the delivery of distinct natural numbers over a transition matrix of four nucleotides to find all occurrences of a DNA pattern in a given string. My algorithm has only Theta(n - 1) time complexity for the worst case with n to be the length of a given string s for a DNA pattern p of length m to be searched on.
  • Keywords
    DNA; biology computing; computational complexity; DNA pattern; computational biology; linear time filtering approach; nucleotides; searching techniques; string matching; time complexity; transition matrix; Computer science; DNA; Filtering; Frequency; Genetics; Matched filters; Nonlinear filters; Pattern matching; Sequences; Table lookup;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Intelligent Sensing and Information Processing, 2006. ICISIP 2006. Fourth International Conference on
  • Conference_Location
    Bangalore
  • Print_ISBN
    1-4244-0612-9
  • Electronic_ISBN
    1-4244-0612-9
  • Type

    conf

  • DOI
    10.1109/ICISIP.2006.4286078
  • Filename
    4286078