Finding all Maximal Palindromes in a Weighted Sequence with the Constraint of the Probability of Appearance
Date Issued
2008
Date
2008
Author(s)
Wang, Yu-Tsun
Abstract
A weighted sequence X is a sequence of positions, and each position stands for a character. Each character associated with a position is assigned a weight. The weight models the probability of appearance of the character associated with that position in a molecular sequence. This model for a weighted sequence can stand for a DNA assembly process. Because DNA is a very large string, only a small amount of DNA can be sequenced in a single read in a laboratory. Thus, a DNA sequence is divided into many short segments and we need to reassemble it to get an entire genome. Reassembling a DNA sequence is a process for handling the uncertainty. The concept of uncertainty associated with some position is considered as that each character has its probability of appearance at that position. The probability of appearance of a word generated from X is calculated by multiplying the relative probability of appearance of each character in every position. In this thesis, we present a linear-time algorithm for finding all maximal palindromes with probability of appearance greater than or equal to 1/k on a weighted sequence. Because palindromes on a DNA sequence may stand for some special meaning for creatures, our algorithm may be a choice for scientists to find all palindromes with the constraint of probability of appearance on a DNA sequence.
Subjects
Weighted Sequence
Palindrome
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922112-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):89c4b25aded6b5276c139b50034da008