Features

In this section are explained in detail the capabilities of the library and some implementation details. PhylogeneticTrees and MSA are the two programs that use the built library.

For a preliminary overview and explanation of Phylogenetic classes visit the Introduction page.

PhylogeneticTrees

This program calculates phylogenetic trees for the sequences provided as FASTA input. It is possible to provide the scoring matrix as input or it can be dynamically calculated using global, local or freeshift alignments. Supported algorithms are UPGMA and NJ, the tree is generated in the Newick tree format.

The first step to construct a phylogenetic tree is to obtain a distance between all the input sequences. Pairwise alignments between each sequence can be performed with the algorithms package Align2:

• With Needleman-Wunsch-Gotoh global alignment
• With Smith-Waterman local alignment
• With Free-shift alignment

Each alignment using the default substitution matrix Blosum 30, open gap penalty 10 and extension gap penalty 0.1. Alternatively you can specify a custom distance matrix through file.

Once you have the pairwise alignment distances are calculated in DistanceMatrix class, method calculateDistance. These scores are calculated as 1 minus the number of identities in the best alignment divided by the length of the shorter sequence. The class can be extended and is possible to override calculateDistance virtual method to obtain alternatives distances score.

From the distance matrix the hierarchical clustering can be accomplished in two ways:

• UPGMA (Unweighted Pair Group Method with Arithmetic Mean): produce a phylogenetic rooted tree in a simple bottom-up way.
• NJ (Neighbor joining): produce a phylogenetic unrooted tree according to the balanced minimum evolution. Optionally you can build a rooted tree with 'mid-point' method.

The phylogenetic tree is output in Newick format. To build a phylogenetic tree with UPGMA:

PhylogeneticTrees  --in input.fasta --upgma --out tree.newick

The output will be something like:

VICTOR - Phylogenetic trees generator

Start of Pairwise alignments
Aligning...

Sequences ( 1: 2) Aligned. Identity Score:  87.81 Score: 80.12
Sequences ( 1: 3) Aligned. Identity Score:  52.74 Score: 43.27
...

Performing UPGMA clustering

Exporting phylogenetic tree in the Newick format...
Writing newick file tree.newick

MSA

This program is an implementation of ClustalW (Thompson, Higgins & Gibson, 1994), one variant of the progressive method for multiple sequence alignment. Guide tree is builded with NJ (or UPGMA) and provided as output in the Newick tree format. Input must be provided as FASTA format, it is possible to provide also the scoring matrix as input or it can be dynamically calculated using global, local or freeshift alignments.

The program builds first the phylogenetic tree rooted as described in the previous section, through:

• UPGMA
• NJ

On the basis of the tree obtained (guides tree) are executed a series of progressive alignments between the various nodes of the tree, starting from the leaves up to the root. The progressive alignments can be obtained with:

• PAM matrices
• BLOSUM Matrices

You need not to specify exactly which one (e.g. Blosum 62 or 30) the program will be select the most suitable matrix during execution.

The most divergent sequences (most different on average from all of the other sequences) are usually the most difficult to align correctly. It is sometimes better to delay the incorporation of these sequences until all of the more easily aligned sequences are merged first. This can be done setting the cutoff value (default 0.4).

The result of the multiple alignment can be in:

• Fasta format
• Clustal format

To obtain a multiple alignment:

Msa --in hem_b.fasta --upgma --outMsa result.fasta --outNewick guideTree.newick

The output will be something like:

VICTOR - Multiple sequence alignment generator

Start of Pairwise alignments
Aligning...

Sequences ( 1: 2) Aligned. Identity Score:  87.81 Score: 80.12
Sequences ( 1: 3) Aligned. Identity Score:  52.74 Score: 43.27
...

Performing UPGMA clustering
Start of Multiple Alignment

Aligning...
Sequences:   2  Score: 545.44
Sequences:   2  Score: 55.95
...

Writing newick file guideTree.newick
Writing multiple alignment file result.fasta