Hi Ryan, On Thu, 2009-12-17 at 09:22 -0800, Ryan Tewhey wrote: > Hi, First off thanks for the great program. I am using it to align 30-50 very > closely related genomes. ProgressiveMauve does a much better job at a > fraction of the time than existing applications. But I am running into one > small and I feel probably correctable error. Regions where a strain or two > has a large (5-20kb) deletion relative to other strains the alignment gets > slightly messed up. The aligner for some reason is introducing breaks in the > alignment of other strains and failing to correctly align all of the strains > within that region. I am assuming that there may be a gap penalty parameter > that I could increase to prevent this. This leads to my question, what are > the defaults for the gap penalty parameters of progressiveMauve? I don't even > know what value to start with for most of the parameters. Since I know where > most of the large insertions are, introducing hardmasked sequence at the site > seems to alleviate the problem. But I feel this is kind of hack on my part > and tuning the aligner to correctly perform the alignment would be ideal.
The short answer is "it's complicated." The long answer is that progressiveMauve's handling of large regions of differential gene content is predominantly affected by three aspects of the algorithm which I'll address in turn: local alignment generation (anchors/multi-MUMs), removal of spurious anchors (breakpoint elimination), and the homology HMM. There are command-line parameters that can be given to progressiveMauve that will change its behavior in each of these phases of the algorithm, and you might find some non-default setting works better for your dataset. Local alignment generation is the process by which high-scoring local alignments among two or more of the genomes are identified. The approach taken by progressiveMauve is to be liberal (or sensitive) with the initial anchor generation, allowing small local alignments to be found that may not represent true homology. Those local alignments are later subject to criteria that remove the non-homologous regions. The size of the initial local alignments can be set on the command-line, the argument is --seed-weight=<number> where <number> can be something ranging from 7 to 23 or so. The weight of a seed corresponds to the number of "1" entries in a spaced seed pattern, as commonly used in the alignment literature on spaced seeds. See also the publication mentioned below. In your case, larger numbers might help to prevent anchors in regions that shouldn't be getting aligned. The next relevant phase of alignment is the breakpoint elimination. That process removes local alignments that if included, would indicate small, poorly supported rearrangements of the genome. The score for a rearranged segment is calculated using a scaled nucleotide substitution matrix. The minimum score to include a segment (after scaling of the score based on expected organism divergence) can be set with --min-scaled-penalty, while the pre-scaled score can be set with --weight. The values used by progressiveMauve for these parameters get printed to output when the program runs, so you can find out what values are being used for your dataset and change them as necessary. These parameters are probably more relevant to your issue than the seed-weight parameter mentioned above. The final relevant alignment phase is application of the Homology HMM to remove spurious alignments of unrelated sequence. This happens after all genomes are aligned. The relevant parameters --hmm-p-go-homologous, --hmm-p-go-unrelated, and --hmm-identity. For resequencing datasets, you may want to set --hmm-identity higher. It specifies the expected level of sequence identity throughout the genome and is set by default to 0.7 (70%) to be sensitive to cross-species comparisons, but a more stringent expectation may be appropriate in your case. The other parameters effectively correspond to gap open and extension penalties, and have an effect on the expected gap length in the final alignment. The relationship is defined by the structure of the hidden Markov Model, as described in this publication: http://doi.ieeecomputersociety.org/10.1109/TCBB.2009.9 These parameters may be the most pertinent to your issue. Incidentally, it is possible to apply different values for these parameters to an alignment without having to recompute the whole alignment. If you have an alignment XMFA file called "my_aln.xmfa" for example, the homology HMM can be applied with the following command: progressiveMauve --apply-backbone=my_aln.xmfa --output=new_aln.xmfa and of course add any of --hmm-p-go-homologous, --hmm-p-go-unrelated, or --hmm-identity as desired. The complete progressiveMauve algorithm description is available in this manuscript, which will probably lend some helpful context to the above suggestions: http://arxiv.org/pdf/0910.5780 -Aaron ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ Mauve-users mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/mauve-users
