Title |
MissMax: alignment-free sequence comparison with mismatches through filtering and heuristics
|
---|---|
Published in |
Algorithms for Molecular Biology, April 2016
|
DOI | 10.1186/s13015-016-0072-x |
Pubmed ID | |
Authors |
Cinzia Pizzi |
Abstract |
Measuring sequence similarity is central for many problems in bioinformatics. In several contexts alignment-free techniques based on exact occurrences of substrings are faster, but also less accurate, than alignment-based approaches. Recently, several studies attempted to bridge the accuracy gap with the introduction of approximate matches in the definition of composition-based similarity measures. In this work we present MissMax, an exact algorithm for the computation of the longest common substring with mismatches between each suffix of a sequence x and a sequence y. This collection of statistics is useful for the computation of two similarity measures: the longest and the average common substring with k mismatches. As a further contribution we provide a "relaxed" version of MissMax that does not guarantee the exact solution, but it is faster in practice and still very precise. |
X Demographics
Geographical breakdown
Country | Count | As % |
---|---|---|
Unknown | 1 | 100% |
Demographic breakdown
Type | Count | As % |
---|---|---|
Members of the public | 1 | 100% |
Mendeley readers
Geographical breakdown
Country | Count | As % |
---|---|---|
Unknown | 13 | 100% |
Demographic breakdown
Readers by professional status | Count | As % |
---|---|---|
Student > Master | 5 | 38% |
Student > Ph. D. Student | 2 | 15% |
Professor > Associate Professor | 2 | 15% |
Researcher | 1 | 8% |
Professor | 1 | 8% |
Other | 0 | 0% |
Unknown | 2 | 15% |
Readers by discipline | Count | As % |
---|---|---|
Computer Science | 3 | 23% |
Agricultural and Biological Sciences | 3 | 23% |
Biochemistry, Genetics and Molecular Biology | 2 | 15% |
Physics and Astronomy | 1 | 8% |
Unknown | 4 | 31% |