title: BpMatch: an efficient algorithm for a segmental analysis of genomic sequences.
abstract: Here, we propose BpMatch: an algorithm that, working on a suitably modified suffix-tree data structure, is able to compute, in a fast and efficient way, the coverage of a source sequence S on a target sequence T, by taking into account direct and reverse segments, eventually overlapped. Using BpMatch, the operator should define a priori, the minimum length l of a segment and the minimum number of occurrences minRep, so that only segments longer than l and having a number of occurrences greater than minRep are considered to be significant. BpMatch outputs the significant segments found and the computed segment-based distance. On the worst case, assuming the alphabet dimension d is a constant, the time required by BpMatch to calculate the coverage is O(l²n). On the average, by setting l ≥ 2 log(d)(n), the time required to calculate the coverage is only O(n). BpMatch, thanks to the minRep parameter, can also be used to perform a self-covering: to cover a sequence using segments coming from itself, by avoiding the trivial solution of having a single segment coincident with the whole sequence. The result of the self-covering approach is a spectral representation of the repeats contained in the sequence. BpMatch is freely available on: www.sourceforge.net/projects/bpmatch.
authors.affiliation: Noname Research, via dell’Ozeretto 3, Pisa 56100, Italy. pangon@gmail.com
authors.forename: Claudio
authors.initials: C
authors.lastname: Felicioli
authors.forename: Roberto
authors.initials: R
authors.lastname: Marangoni
mesh_terms: D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D002877:Chromosomes, Human; D016678:Genome; D023281:Genomics / Q000379:methods*; D006801:Humans; D020407:Internet; D051379:Mice; D008957:Models, Genetic; D008969:Molecular Sequence Data; D012091:Repetitive Sequences, Nucleic Acid; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software