Applicability of the multiple alignment algorithm for detection of weak patterns: periodically distributed DNA pattern as a study case.
BACKGROUND
A nucleosome DNA positioning pattern is known to be one of the weakest (highly degenerated) patterns. The alignment procedure that has been developed recently for the extraction of such a pattern is based on a statistical matching of the sequences, and its success depends on the pattern/background ratio in the individual sequences and in the generated pattern. The heuristic nature of the method and distinctive properties of the pattern bring up the question of efficiency and sensitivity in the procedure. This paper presents a method of verification for this multiple sequence alignment algorithm.


RESULTS
To verify the applicability of the multiple alignment approach, we constructed a set of sequences carrying the hidden pattern. The pattern was presented by weak ('signal') oscillations of occurrences of AA and TT dinucleotides along otherwise random sequences. Only a few dinucleotides of any given 145 base long sequence would correspond to the signal, appearing in about the same phase within the simulated periodic pattern. The novelty of our simulation approach is that we simulated a database as a whole, as opposed to simulating each sequence separately. The correlation between the hidden pattern and a sequence from the database is negligible on average, but our statistical multicycle alignment procedure produced the pattern with attributes very close to the simulated ones. The accuracy of the procedure was tested and calibrated. The presence in a typical sequence of as little as three dinucleotides corresponding to the signal is sufficient to generate (detect) the pattern hidden in a collection of 204 sequences.
Bolshoy
A
A
Department of Membranes Research and Biophysics, Weizmann Institute of Science, Rehovot, Israel. bmbolsho@dapsas1.weizmann.ac.il
Ioshikhes
I
I
Trifonov
E N
EN
D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D016208:Databases, Factual; D010363:Pattern Recognition, Automated; D016415:Sequence Alignment