Statistical identification of uniformly mutated segments within repeats
UNSPECIFIED (2002) Statistical identification of uniformly mutated segments within repeats. In: 13th Annual Symposium on Combinatorial Pattern Matching, JUL 03-05, 2002, FUKUOKA, JAPAN.Full text not available from this repository.
Given a long string of characters from a constant size (w.l.o.g. binary) alphabet we present an algorithm to determine whether its characters have been generated by a single i.i.d. random source. More specifically, consider all possible k-coin models for generating a binary string S, where each bit of S is generated via an independent toss of one of the k coins in the model. The choice of which coin to toss is decided by a random walk on the set of coins where the probability of a coin change is much lower than the probability of using the same coin repeatedly. We present a statistical test procedure which, for any given S, determines whether the a posteriori probability for k = 1 is higher than for any other k > 1. Our algorithm runs in time O(l(4) log l), where e is the length of S, through a dynamic programming approach which exploits the convexity of the a posteriori probability for k. The problem we consider arises from two critical applications in analyzing long alignments between pairs of genomic sequences. A high alignment score between two DNA sequences usually indicates an evolutionary relationship, i.e. that the sequences have been generated as a result of one or more copy events followed by random point mutations. Such sequences may include functional regions (e.g. exons) as well as nonfunctional ones (e.g. introns). Functional regions with critical importance exhibit much lower mutation rates than non-functional DNA (or DNA with non-critical functionality) due to selective pressures for conserving such regions. As a result, given an alignment between two highly similar genome sequences, it may be possible to distinguish functional regions from non-functional ones using variations in the mutation rate. Our test provides means for determining variations in the mutation rate and thus checking the existence of DNA regions of varying degrees of functionality. A second application for our test is in determining whether two highly similar, thus evolutionarily related, genome segments are the result of a single copy event or of a complex series of copies. This is particularly an issue in evolutionary studies of genome regions rich with repeat segments (especially non-functional tandemly repeated DNA). Our approach can be used to distinguish simple copies from complex repeats again by exploiting variations in mutation rates.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||COMBINATORIAL PATTERN MATCHING|
|Editor:||Apostolico, A and Takeda, M|
|Number of Pages:||13|
|Page Range:||pp. 249-261|
|Title of Event:||13th Annual Symposium on Combinatorial Pattern Matching|
|Location of Event:||FUKUOKA, JAPAN|
|Date(s) of Event:||JUL 03-05, 2002|
Actions (login required)