Constrained Sequence Alignment
Dr. Abdullah Arslan
Department of Computer Science
Date:
Time:
Location: 367 Votey
Abstract
Sequence alignment is an important problem in computational biology. The objective of sequence alignment is to detect in given biological sequences similar regions which may reveal evolutionary relatedness or common functionality. Ordinarily sequence alignment is defined as an optimization problem in which we aim to find an alignment with maximum score without considering restrictions on the alignments. However, it has been noted that biologists favor integrating their knowledge about common patterns, or structures into the alignment process to obtain biologically more meaningful similarities. This has given rise to a number of constrained sequence alignment problems where optimal alignments sought are required to contain a given pattern (exactly or within small differences). The pattern can be described by a regular expression (e.g. a PROSITE motif) as well as it can be a simple sequence. In this talk I will discuss several constrained sequence alignment problems, and I will present the algorithms we have developed for them.