Paper Info
Title
MissMax: alignment-free sequence comparison with mismatches through filtering and heuristics.
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.
Year
DOI
Venue
2016
10.1186/s13015-016-0072-x
Algorithms for Molecular Biology
Keywords
Field
DocType
Alignment free,Compositional approaches,Mismatches,Phylogenetic analysis,Sequence similarity
Data mining,Substring,Computer science,Filter (signal processing),Heuristics,Bioinformatics
Journal
Volume
Issue
ISSN
11
1
1748-7188
Citations 
PageRank 
References 
8
0.48
19
Authors
1
Name
Order
Citations
PageRank
Cinzia Pizzi113915.73