By downloading this code you agree to the
Source Code Use License (PDF). |
{ version = 2.70; (* of malign.p 2018 Sep 12} (* begin module describe.malign *) (* name malign: optimal alignment of a book, based on minimum uncertainty synopsis malign(inst: in, book: in, malignp: in, uncert: out, newalign: out, optalign: out, optinst: out, malignxyin: out, output: out) files inst: delila instructions of the form 'get from 56 -5 to 56 +10;' book: the book generated by delila using inst malignp: parameter file with the following parameters: winleft, winright: left and right ends of window for calculating uncertainty, relative to aligned base shiftmin, shiftmax: minimum and maximum shift of aligned base iseed: integer random seed nranseq: number of random sequences, or 0 to use sequences in book nshuffle: number of times to redo alignment after random shuffle ifpaired: 1 to treat each pair of sequences as complementary strands, 0 not to standout: output run #, pass # and H to standard output every pass if 1, every run if 0, or not at all if -1 npassout: output H and alignment every npassout passes to file newalign, or only at end of runs if zero, or not at all if -1 nshiftout: output L and H(L) every nshiftout sequence shifts (to file uncert), or only at end of passes if zero, or not at all if -1 tolerance: tolerance in change of H ntolpass: maximum number of passes with change below tolerance new parameter allowed but not required (default is i): alignmenttype: char; 'f' means alignment by First internal coordinate base, 'b' means alignment by Book, 'i' means alignment by Instructions. See the alist program for more information. Normally one will align by delila instructions. If this parameter is 'f', then the first base of the book is considered the zero base and if it is 'b' then the zero base is given by the coordinates of each piece in the book. uncert: uncertainty as function of position, for the last run, at the end of each pass or after selected number of sequence shifts Controlled by variable nshiftout. newalign: values of H and the relative alignments; starting, final, and intermediate if selected. Controlled by variable npassout. optalign: user-readable listing of unique optimal relative alignments and number of times each was achieved optinst: list of unique optimal alignments in absolute coordinates, to be used to make inst file for selected alignment This file is like optalign, but the coordinates are for the original sequence. malignxyin: a list of the number of occurrences of alignments and their H values in bits. This may be plotted with xyplo, as described in the paper. Each line contains these numbers: rank: from 1 to the number of alignment classes occurrences: how many times the class was found H: the uncertainty of the alignment, in bits R: the information content of the alignment, in bits with small sample correction. description Given a book of aligned sequences, this program searches for the alignment of the sequences that has the lowest uncertainty, i.e. the highest value of Rsequence. The user specifies the "window" of bases within which uncertainty is calculated, and the maximum number of bases that each sequence is allowed to shift from the original alignment. The program considers each sequence in turn, shifting it to an alignment with minimum uncertainty while holding the other sequences fixed. A "pass" is complete when all sequences have been considered. A "run" is complete when no alignments have changed in the preceding pass, and the alignment is then considered "optimal". The first run starts with the original alignment; every run after that starts with a "shuffled" alignment obtained by shifting each sequence independently by a random amount between the allowed limits. The program maintains a list of all of the unique optimal alignments achieved from these starting alignments, and it outputs them in order of increasing uncertainty. In version 2.33 and earlier, the program did not keep track of the organism and chromosome names in bestinst. This file is now superceeded by the malin program which copies the inst file to cinst and modifies it according to one of the alignments in optinst. Statistical testing We have found a method to work with malign that gives reliable results. First run malign many times (e.g. 100) on the sites of interest using the timeseed (with at least 1 second delay between runs so that the timeseed changes). Collect the information content distribution. Then extract the same length sequences from random places on the host organism or use comp to get the composition of the host and the markov program to generate a random set. Run malign again with the same number of sequences and parameters. If you find that the two distributions differ significantly (using the ttest program) then you've got something. This was useful for us in a paper we are just finishing - in one case we see a distinct pattern clearly distinguishable from the random host sequences and in another the distributions were identical. ******************************************************************************** Summary of file output: Malign produces: uncert, newalign, optalign, optinst, malignxyin, output -- output -- Line 7 of "malignp" controls output Parameter: 1 - every run, pass, and uncertainty will be outputed to the screen 0 - only the lowest uncertainty run will be outputed -1 - nothing will be outputed *NOTE* no file will be produced regardless of the parameter -- newalign -- Line 8 of "malignp" controls newalign Parameter: 1 - produces a full newalign file 0 - produces a smaller newalign file (about half the size) -1 - produces no newalign file *NOTE* this is the largest file produced and is unnecessary -- uncert -- Line 9 of "malignp" controls uncert Parameter: 1 - produces a full uncert file 0 - produces a smaller uncert file (about half the size) -1 - produces an empty uncert file *NOTE* file will be produced regardless of the parameter, however this file is large and unnecessary -- optalign -- *NOTE* this file will always be produced and is needed to run malin -- optinst -- *NOTE* this file will always be produced and is needed to run malin -- malignxyin -- *NOTE* this file will always be produced and can be used to plot data using xyplo If you set our parameters so newalign and uncert are not created, this can save some space. (Thanks to Brent M. Jewett for compiling this information on 2001 Feb 7.) ******************************************************************************** documentation A paper describing the algorithm in detail is available from <A href="https://alum.mit.edu/www/toms/ftp/malign.pdf" >https://alum.mit.edu/www/toms/ftp/malign.pdf</A> @article{Schneider.Mastronarde.malign, author = "T. D. Schneider and D. Mastronarde", title = "{Fast} multiple alignment of ungapped {DNA} sequences using information theory and a relaxation method", journal = "Discrete Applied Mathematics", note = "https://alum.mit.edu/www/toms/ftp/malign.pdf", volume = "71", pages = "259-268", year = "1996"} The use of malign to align sequences with a subtle pattern is described in: @article{Toledano1994, author = "M. B. Toledano and I. Kullik and F. Trinh and P. T. Baird and T. D. Schneider and G. Storz", title = "Redox-Dependent Shift of {OxyR-DNA} Contacts Along An Extended {DNA} Binding Site: A Mechanism for Differential Promoter Selection", journal = "Cell", volume = "78", pages = "897-909", year = "1994"} For how the information content and small sample correction are computed: @article{Schneider1986, author = "T. D. Schneider and G. D. Stormo and L. Gold and A. Ehrenfeucht", title = "Information content of binding sites on nucleotide sequences", journal = "J. Mol. Biol.", volume = "188", pages = "415-431", year = "1986"} see also Paper Schneider.Mastronarde.malign: https://alum.mit.edu/www/toms/paper/malign/ Program to graph the malignxyin file: xyplo.p You can use the malign.xyplop file for the xyplop and the malignxyin for the xyin. Set the xyplom to be empty. I ALWAYS make this graph to see what is going on. Program to make delila instructions from nth alignment of malign: malin.p Example parameter file, malignp: malignp A COMPLETE SET FOR DEMONSTRATING THE PROGRAM malign.inst instructions for grabbing the first 6 EcoRI sites on the E. coli genome, but messed up by setting the last digit to zero malign.book The Delila book corresponding to malign.inst malign.malignp Parameter file for malign to realign the inst and book. If one uses malin to pick the first alignment, one finds that they are correctly realigned: - + 1--------- +++++++++1 098765432101234567890 ..................... EcoRI U00096 3842 + 1 cgacctgccggaattcagcct U00096 12889 + 2 tctggttgaagaattcaagaa U00096 32545 + 3 tcagggtatcgaattcgacta U00096 50237 + 4 ggtattcagcgaattccacga U00096 56282 + 5 agaggtagcggaattcgttct U00096 96860 + 6 gctacgtcaggaattcctgct Program for listing aligned sequences, as above: alist.p Program for comparing two distributions: ttest.p author David Mastronarde and Tom Schneider bugs The realignment algorithm, which shifts all sequences by the same amount to attempt to keep the window near its original position, is somewhat ad hoc in nature and the effects of different settings for it parameters have not been explored. If the window spans two real sites with competing alignments, many optimal but meaningless alignments with similar uncertainties may be obtained. The random sequences can't be examined. For the computation of Rsequence, composition is assumed to be equiprobable, there is no provision for reading in a cmp file yet. technical notes The malignxyin file Rsequence has the small sample correction. The choice between the estimate and the more exact computation is determined by constant "kickover". The constant maxlen is one longer than the longest sequence. The constant maxnseq is the maximum number of sequences. *) (* end module describe.malign *) {This manual page was created by makman 1.45}{created by htmlink 1.62}