Item

Abstract

Background: Comparative analysis of homologous sequences enables the understanding of evolutionary patterns
at the molecular level, unraveling the functional constraints that shaped the underlying genes. Bioinformatic pipelines
for comparative sequence analysis typically include procedures for (i) alignment quality assessment and (ii) control of
sequence redundancy. An additional, underassessed step is the control of the amount and distribution of missing
data in sequence alignments. While the number of sequences available for a given gene typically increases with time,
the site-specific coverage of each alignment position remains highly variable because of differences in sequencing
and annotation quality, or simply because of biological variation. For any given alignment-based analysis, the
selection of sequences thus defines a trade-off between the species representation and the quantity of sites with
sufficient coverage to be included in the subsequent analyses.
Results: We introduce an algorithm for the optimization of sequence alignments according to the number of
sequences vs. number of sites trade-off. The algorithm uses a guide tree to compute scores for each bipartition of the
alignment, allowing the recursive selection of sequence subsets with optimal combinations of sequence and site
numbers. By applying our methods to two large data sets of several thousands of gene families, we show that
significant site-specific coverage increases can be achieved while controlling for the species representation.
Conclusions: The algorithm introduced in this work allows the control of the distribution of missing data in any
sequence alignment by removing sequences to increase the number of sites with a defined minimum coverage. We
advocate that our missing data optimization procedure in an important step which should be considered in
comparative analysis pipelines, together with alignment quality assessment and control of sampled diversity. An
open source C++ implementation is available at http://bioweb.me/physamp.