| The analysis of DNA sequences is a significant component of the human genome project. Several strongly repetitive structures in DNA are associated with genetic diseases, while weaker repetitive structures are thought to be representative of historical events associated with sequence repetition. To detect these repetitive sequences, a new algorithm, the periodicity explorer algorithm, is developed.; The algorithm uses a short-time periodicity transform to compute the closest periodic sequence of fixed length at each nucleotide position to be analyzed. Each original subsequence is then compared to its closest periodic sequence to provide a quantitative measure of the amount of repetition. The algorithm also provides a potentially useful visualization of periodic patterns in DNA sequences by the use of a graphical display of the relative energy in the optimal periodic projections of the analyzed sequences, i.e., the DNA periodogram. Computationally, the algorithm is linear in the length of the analyzed sequence. |
