Realignment Methods

Horizontal-oriented realignment in MSA tools

1. PRRP (1996)

Its horizontal-oriented refinement idea is the similar as MUSCLE.

• FTP

2. MLAGAN (2002)

The tool's realignment is optional, which is also single-type partitioning, following:

1. Find segments of sequence Xi that align better than a given cutoff, in the existing multiple alignment. These segments are the anchors between Xi and the other sequences.

2. Realign Xi to the multiple alignment of the other sequences with LAGAN.

• MLAGAN's homepage

3. MAFFT (2002)

Tree-dependent partitioning realignment

In one cycle of iterative refinement, all the branches in the guide tree are tried as partitioning points.

• MAFFT's homepage

4. MUSCLE3 (2004)

Tree-dependent partitioning realignment:

1. Randomly divide the alignment into two profiles based on an edge of TREE.

2. A new alignment is obtained by realigning the two profiles.

3. If the SP score is improved, the new alignment is kept.

Until convergence or until a user‐defined limit is reached.

• MUSCLE's homepage

5. ProbCons (2004)

Random partitioning realignment:

1. Randomly divide the alignment into two profiles.

2. Realign the two profiles.

Until a predefined maximum number of iterations is reached.

• ProbCons's homepage

6. PRIME (2006)

Before the realignment, this tool calculate a distance matrix from the initial alignment, construct a phylogenetic tree from the distance matrix, calculate pair weights from the phylogenetic tree, then iteratively realign the alignment using the phylogenetic tree and the pair weights:

Tree-dependent partitioning realignment:

1. Divide the alignment into two groups based on a randomly chosen branch of the tree.

2. Realign the sequences in each subtree. Get a new alignment until no better weighted SP score is obtained.

Repeat steps from the begining of calculate a distance matrix from the new alignment to iteratively realign until the weighted SP score of the alignment dose not improve anymore.

• The source code link is unavailable.

7. MANGO (2007)

Single-type partitioning realignment:

1. Select one sequence.

2. Realign it with the others.

Until all sequences realign.

• The source code link is unavailable.

8. COBALT (2007)

Tree-dependent partitioning realignment:

1. Partition the current initial alignment into two profiles separated by a edge (Not its longest one.)

2. Realign the two profiles.

For each edge, this repeats up to five times, or as long as the best score from the current iteration improves the best score from the previous iteration by at least 2%.

• (Optional) Perform refinement by determining a new set of constraints and iterative tree-dependent partitioning realignment.

• FTP

9. PRALINE™ (2008)

Tree-dependent partitioning realignment:

1. Partition the current initial alignment into two profiles separated by each edge (one iterative cycle means that each edge of the tree is visited once.)

2. Realign the two profiles.

3. The new alignment is retained only if a higher SP score is achieved.

Until a predefined maximum number of iterations is reached.

• PRALINE's homepage

10. IPAM (2009)

Its horizontal-oriented refinement idea is the same as MUSCLE.

• The source code is not publicized.

11. MSAProbs (2010)

Random partitioning realignment:

1. Randomly divide the alignment into two profiles. (its own pseudo random number generator based on the linear congruential method for random partitioning)

2. Realign the two profiles.

Until a predefined maximum number of iterations is reached.

• [https:msaprobs.sourceforge.net/homepage.htm

12. MSACompro (2011)

Random partitioning realignment:

1. Randomly divide the alignment into two profiles

2. Realign the two profiles.

Until a predefined maximum number of iterations is reached.

• MSACompro's homepage

13. PAAA (2011)

Tree-dependent partitioning realignment:

1. Construct a new guide tree utilizing a new distance matrix based on the MSA.

2. Remove an edge from the new guide tree to obtain two new subtrees.

3. Realign the sequences in each subtree.

4. Align the two profiles associated with the two subtrees to get a global MSA.

Until convergence.

• The source code is not publicized.

14. MMSA (2012)

This tool implements three different horizontal partitioning methods to realign:

1. Random partitioning

2. Tree-dependent partitioning and each time randomly cut a edge of the guiding tree.

3. Tree-dependent partitioning and each edge of the tree is cut only once in the breath-first order.

• The source code link is unavailable.

15. GLProbs (2013)

Random partitioning realignment:

1. Randomly divide the alignment into two profiles

2. Realign the two profiles.

Until convergence or a predefined maximum number of iterations is reached.

• GLProbs's source code

16. Javad Sadri's work (2013)

Tree-dependent partitioning realignment:

1. Randomly select an edge and cut it into two subtrees.

2. Realign the two profiles.

3. If the result is improved, the guide tree is changed. Otherwise, the previous guide tree is retained.

Until a predefined maximum number of iterations is reached.

• The source code is not publicized.

17. Motalign (2013)

Its horizontal-oriented refinement idea is the same as MUSCLE.

• The source code is not publicized.

18. QuickProbs (2014)

Its horizontal-oriented refinement idea is the same as MSAProbs.

QuickProbs2 is the last version.

• QuickProbs's github

19. PnpProbs (2016)

Random partitioning realignment:

1. Randomly divide the alignment into two profiles

2. Realign the two profiles.

Until convergence or a predefined maximum number of iterations is reached.

• PnpProbs's github

20. Pro-malign (2018)

Its realignment does not employ iterative methods.

1. Create two new families based on the distance matrix obtain from the initial alignment.

2. Realign the two families.

• The source code is not publicized.

Realigners based on vertical partitioning

Realigners based on horizontal partitioning

Realigners based on vertical and horizontal partitioning

Realignment in MSA tools

Vertical-oriented realignment in MSA tools