  When analyzing communities of microorganisms from their sequenced DNA, an
important task is taxonomic profiling: enumerating the presence and relative
abundance of all organisms, or merely of all taxa, contained in the sample.
This task can be tackled via compressive-sensing-based approaches, which favor
communities featuring the fewest organisms among those consistent with the
observed DNA data. Despite their successes, these parsimonious approaches
sometimes conflict with biological realism by overlooking organism
similarities. Here, we leverage a recently developed notion of biological
diversity that simultaneously accounts for organism similarities and retains
the optimization strategy underlying compressive-sensing-based approaches. We
demonstrate that minimizing biological diversity still produces sparse
taxonomic profiles and we experimentally validate superiority to existing
compressive-sensing-based approaches. Despite showing that the objective
function is almost never convex and often concave, generally yielding NP-hard
problems, we exhibit ways of representing organism similarities for which
minimizing diversity can be performed via a sequence of linear programs
guaranteed to decrease diversity. Better yet, when biological similarity is
quantified by $k$-mer co-occurrence (a popular notion in bioinformatics),
minimizing diversity actually reduces to one linear program that can utilize
multiple $k$-mer sizes to enhance performance. In proof-of-concept experiments,
we verify that the latter procedure can lead to significant gains when
taxonomically profiling a metagenomic sample, both in terms of reconstruction
accuracy and computational performance. Reproducible code is available at
https://github.com/dkoslicki/MinimizeBiologicalDiversity.
