Catalog Home Page

Efficient algorithms for counting and reporting segregating sites in genomic sequences

Christodoulakis, M., Golding, G.B., Iliopoulos, C.S., Ardila, Y.J.P. and Smyth, W.F. (2007) Efficient algorithms for counting and reporting segregating sites in genomic sequences. Journal of Computational Biology, 14 (7). pp. 1001-1010.

Link to Published Version: http://dx.doi.org/10.1089/cmb.2006.0136
*Subscription may be required

Abstract

The number of segregating sites provides an indicator of the degree of DNA sequence variation that is present in a sample, and has been of great interest to the biological, pharmaceutical and medical professions. In this paper, we first provide linear- and expected-sublinear-time algorithms for finding all the segregating sites of a given set of DNA sequences. We also describe a data structure for tracking segregating sites in a set of sequences, such that every time the set is updated with the insertion of a new sequence or removal of an existing one, the segregating sites are updated accordingly without the need to re-scan the entire set of sequences.

Publication Type: Journal Article
Publisher: Mary Ann Liebert Inc.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27930
Item Control Page Item Control Page