Parsimony

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 $S = \{s_1, .., s_n\}$ with $s_i \in \Sigma^*$ where $\Sigma$ is a finite alphabet. A Multiple Sequence Alignment (MSA) consists of a set of sequences $\mbox{\rm A} = \{ a_1, a_2, .., a_n\}$ with $a_i \in \Sigma^{'*}$ where $\Sigma' = \Sigma \cup \{''\_''\} \not \in \Sigma$. $\forall a_i \in \mbox{\rm A}: \vert a_i\vert=k$. The sequence obtained from $a_i \in \mbox{\rm A}$ by removing all $''\_''$ gap characters is equal to s_i.