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