Efficient algorithms for counting and reporting segregating sites in genomic sequences.
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.
Christodoulakis
Manolis
M
Department of Computer Science, King's College London, London, United Kingdom. manolis@dcs.kcl.ac.uk
Golding
G Brian
GB
Iliopoulos
Costas S
CS
Ardila
Yoan José Pinzón
YJ
Smyth
William F
WF
D000465:Algorithms; D001483:Base Sequence; D014644:Genetic Variation; D016678:Genome; D017422:Sequence Analysis, DNA