الفهرس 
IntroductionOnly 14 pages are availabe for public view
 |  | from | 66 |  |  |
| | | from | 66 | | |
Abstract
Sequence alignment is a way to determine the level of similarity between sequences. It’s is the basic step in many bioinformatics applications like phylogeny tree construction. All alignment approaches try to solve the problem of running time against optimality. On one hand, optimal sequence alignment approaches is costly in time. On the other hand, approxi¬mate approaches may significantly affect the accuracy of the whole application.
In this thesis, an adaptation of Ukkonen string matching algorithm is proposed to fit in sequence alignment applications. While keeping the optimal alignment, the adapted al¬gorithm changes the complexity of alignment to be O(NE) rather than the basic alignment algorithm complexity O(NM). With this new complexity, the new adapted algorithm will be more efficient if the sequences are relatively convergent. Further enhancements in the adapted algorithm are applied to enhance its performance when the database contains diver¬gent sets of sequences.
The adapted algorithm is compared to the basic Needleman-Wunsch algorithm in se¬quence query application. The experimental evaluation shows considerable improvements in performance when applying the new adapted algorithm.