  To cluster sequences given only their read-set representations, one may try
to reconstruct each one from the corresponding read set, and then employ
conventional (dis)similarity measures such as the edit distance on the
assembled sequences. This approach is however problematic and we propose
instead to estimate the similarities directly from the read sets. Our approach
is based on an adaptation of the Monge-Elkan similarity known from the field of
databases. It avoids the NP-hard problem of sequence assembly. For low coverage
data it results in a better approximation of the true sequence similarities and
consequently in better clustering, in comparison to the
first-assemble-then-cluster approach.
