The parsimony methods usually count the number of amino acid or
nucleotide substitutions in a weighted or unweighted manner. They
take a multiple sequence alignment (MSA) as input and minimize the
number of changes to explain the corresponding
evolutionary tree. The construction of an optimal MSA, which is
needed as input, is also NP complete [22]. In addition,
many algorithms for calculating MSAs need an evolutionary tree as
input, which makes the problem circular.

Definition 1.2
Given is a set of sequences
with
where
is a finite alphabet. A Multiple
Sequence Alignment (MSA) consists of a set of sequences
with
where
.
.
The sequence obtained from
by removing all
gap characters is equal to s_{i}.