An enhancement of knuth, morris and pratt algorithm applied in DNA sequence matching / Kenneth M Idos, . and Renz Benson A. Soriano. 6

By: Idos, Kenneth M. and Soriano, Renz Benson A. 4 0 16, [, ] | [, ] |
Contributor(s): 5 6 [] |
Language: Unknown language code Summary language: Unknown language code Original language: Unknown language code Series: ; 201846Edition: Description: 28 cm. 216 ppContent type: text Media type: unmediated Carrier type: volumeISBN: ISSN: 2Other title: 6 []Uniform titles: | | Related works: 1 40 6 []Subject(s): -- 2 -- 0 -- -- | -- 2 -- 0 -- 6 -- | 2 0 -- | -- -- 20 -- | | -- -- -- -- 20 -- | -- -- -- 20 -- --Genre/Form: -- 2 -- Additional physical formats: DDC classification: | LOC classification: | | 2Other classification:
Contents:
Action note: In: Summary: ABSTRACT: In this study, an enhanced algorithm for the traditional pattern matching has been proposed named Kruth, Morris, and Pratt Algorithm. This algorithm is an exact matching algorithm that finds an occurrence of a Pattern in a Text. Pattern searching is an important problem relating on computer science. It can be seen on searching for a given string in notepad, browser or database, pattern searching algorithm are used to show the search results. The researchers find the algorithm the most efficient to its application, DNA Sequencing, by its abilities which are an advantage to other related pattern matching algorithms. The KMP algorithm is independent to the alphabet size, use the notion of border of the string, increases performance, decrease delay and decrease time of comparing. Since a DNA sequence contains only a 4 alphabet size which are A, G, C and T, the algorithm denotes characteristics that is suitable to the application by matching phase. The enhanced algorithm is a modified version of Kruth Morris Pratt algorithm. The researchers recognized KMP algorithm for its commendable characteristics, but in this paper, we proposed an enhancement of the algorithm to make it more effective. The first problem is that the existing algorithm is unable to indicate to what extend a match was found. Second, existing algorithm becomes inaccurate if the Pattern p is preceded by its proper prefix in Text T. And lastly, the existing algorithm becomes slow when Pattern p doesn't have repeating sub-patterns. The researchers came up with objectives to solve the existing problems. First, by using the backtrack methodology, the enhanced algorithm can find the unrecognized overlapping occurrences of the pattern in the Text. Second, to make the algorithm more accurate even the Pattern is preceded by its proper prefix in the Text by using of prefix table and two pre-conditions in searching pattern with its preceded prefix. And, to improve the algorithm's running time complexity given that the Pattern has no repeating sub-patterns by using Bitwise XNOR binary operation to process two characters in parallel, to speed up the pattern matching process. As the new algorithm uses the principle of Finite automata which is used by KMP algorithm and Bitwise XNOR operation to speed up the character match, it shows some reasonable performance improvement. Also this new algorithm is easy to implement as it doesn't require any additional or complex data structure and suitable for DNA sequence search. Other editions:
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)

Thesis: (BSCS major in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2018. 56

5

ABSTRACT: In this study, an enhanced algorithm for the traditional pattern matching has been proposed named Kruth, Morris, and Pratt Algorithm. This algorithm is an exact matching algorithm that finds an occurrence of a Pattern in a Text. Pattern searching is an important problem relating on computer science. It can be seen on searching for a given string in notepad, browser or database, pattern searching algorithm are used to show the search results. The researchers find the algorithm the most efficient to its application, DNA Sequencing, by its abilities which are an advantage to other related pattern matching algorithms. The KMP algorithm is independent to the alphabet size, use the notion of border of the string, increases performance, decrease delay and decrease time of comparing. Since a DNA sequence contains only a 4 alphabet size which are A, G, C and T, the algorithm denotes characteristics that is suitable to the application by matching phase. The enhanced algorithm is a modified version of Kruth Morris Pratt algorithm. The researchers recognized KMP algorithm for its commendable characteristics, but in this paper, we proposed an enhancement of the algorithm to make it more effective. The first problem is that the existing algorithm is unable to indicate to what extend a match was found. Second, existing algorithm becomes inaccurate if the Pattern p is preceded by its proper prefix in Text T. And lastly, the existing algorithm becomes slow when Pattern p doesn't have repeating sub-patterns. The researchers came up with objectives to solve the existing problems. First, by using the backtrack methodology, the enhanced algorithm can find the unrecognized overlapping occurrences of the pattern in the Text. Second, to make the algorithm more accurate even the Pattern is preceded by its proper prefix in the Text by using of prefix table and two pre-conditions in searching pattern with its preceded prefix. And, to improve the algorithm's running time complexity given that the Pattern has no repeating sub-patterns by using Bitwise XNOR binary operation to process two characters in parallel, to speed up the pattern matching process. As the new algorithm uses the principle of Finite automata which is used by KMP algorithm and Bitwise XNOR operation to speed up the character match, it shows some reasonable performance improvement. Also this new algorithm is easy to implement as it doesn't require any additional or complex data structure and suitable for DNA sequence search.

5

There are no comments for this item.

to post a comment.

© Copyright 2024 Phoenix Library Management System - Pinnacle Technologies, Inc. All Rights Reserved.