Merging covering arrays and compressing multiple sequence alignments Original Research Article

Covering arrays have been extensively studied, in part because of their applications in testing interacting software components. In this setting, fast and flexible methods are needed to construct covering arrays of close-to-minimum size. However testing scenarios often impose additional structure on the tests that can be selected. We extend a greedy method to construct test suites for complex systems that have a hierarchical structure in which components combine to form subsystems, which in turn form larger subsystems, until the entire system is formed. The algorithm for merging covering arrays that we propose is then shown to have further potential application in the compression of multiple sequence alignments of genomic data.