Multiple-changepoint testing for an alternating segments model of a binary sequence

A binary sequence may give the appearance of being composed of alternating segments with relatively high and relatively low probability of success. Determining whether such an alternating pattern is significant is a multiple-changepoint problem where the number of segments and their success probabilities are unknown, with the added constraint of segment alternation. A dynamic programming method for determining the optimal segmentation into a given number of segments is provided. Given this, a variation on the simulation method of Venter and Steel (1996, Computational Statistics and Data Analysis 22, 481-504) may be employed to test the null hypothesis of a homogeneous sequence as well as to estimate the number and location of changepoints. A sample application, the assessment of the possibility of genetic recombination in HIV sequences, is presented.