[Bioperl-l] Re: Another update for my alignment module

[Yee Man Chan]

Hi Aaron,

	The text after my signature will be the synopsis. My code is not
updated yet to fit the synopsis. I should be able to update it by
tomorrow. Tell me what you think about the synopsis.

Thanks 
Yee Man

NAME
	dpAlign - Perl extension to do dynamic programming sequence alignment

SYNOPSIS
	use dpAlign;
	use Bio::SeqIO;
	use Bio::SimpleAlign;
	use Bio::AlignIO;

	$seq1 = new Bio::SeqIO(-file => $ARGV[0]. -format => 'fasta');
	$seq2 = new Bio::SeqIO(-file => $ARGV[1]. -format => 'fasta');

	# create a dpAlign object
	$factory = new dpAlign(-match => 3,
			   -mismatch => -1,
			   -gap => 3,
			   -ext => 1,
			   -alg => dpAlign::DPALIGN_LOCAL_MILLER_MYERS);

	# actually do the alignment
	$out = $factory->pairwise_alignment($seq1->next_seq, $seq2->next_seq);
	$alnout = new Bio::AlignIO(-format => 'pfam', -fh => \*STDOUT);
	$alnout->write_aln($out);

DESCRIPTION
	Dynamic Programming approach is considered to be the most
	sensitive way to align two biological sequences. There are
	currently three major types of dynamic programming algorithms:
	Global Alignment, Local Alignment and Ends-free Alignment.

	Global Alignment compares two sequences in their entirety.
	By inserting gaps in the two sequences, it aligns two 
	sequences to minimize the edit distance as defined by the
	gap cost function and the substitution matrix. Global Alignment
	is generally applied to two sequences that are very similar 
	in length and content.

	Local Alignment instead attempts to find out the subsequences 
	that has the minimal edit distance among all possible subsequences.
	It is good for sequences that has a stretch of subsequences
	that are similar to each other.

	Ends-free Alignment is a special case of Global Alignment. There
	are no gap penalty imposed for the gaps that extended from 
	the end points of two sequences. Therefore it will be a good 
	application when you think one sequence is contained by the 
	other or when you think two sequences overlap each other. 

	Dynamic Programming was first introduced by Needleman-Wunsch (1970)
	to globally align two sequences. The idea of local alignment
	was later introduced by Smith-Waterman (1981). Gotoh (1982) 
	improved both algorithms by introducing auxillary arrays that
	reduced the time complexity of the algorithms to O(m*n). 
	Miller-Myers (1988) exploits the divide-and-conquer idea 
	introduced by Hirschberg (1975) to solve the affine gap cost
	dynamic programming using only linear space. It is accepted 
	that Miller-Myers implementation is the fastest and using the
	least memory that is truly equivalent to original algorithm
	introduced by Needleman-Wunsch. Phil Green (?? yr) introduced
	heuristics to skip the calculation of some cells. However,
	his approach is only good for calculating the minimum edit 
	distance and find out the corresponding subsequences (aka 
	search phase). The most popular dynamic programming alignment 
	program ssearch uses Phil Green's algorithm to find the 
	subsequences and then Miller-Myers's algorithm to find the 
	actual alignment. (aka alignment phase)

	The current implementation supports local alignment of
	either DNA sequences or protein sequences. It allows you 
	to specify either the Phil Green (DPALIGN_LOCAL_GREEN)
	or Miller-Myers (DPALIGN_LOCAL_MILLER_MYERS). For DNA 
	alignment, you can specify the scores for match, mismatch,
	gap opening cost and gap extension cost. For protein 
	alignment, it is using BLOSUM62 by default. Currently the
	substitution matrix is not configurable.

DEPENDENCIES
	To use this module, please install a full version of bioperl.
	It was tested to work with bioperl-1.1 and above. 

TO-DO
	1) Allow custom substitution matrix.

	2) Support Global Alignment.

	3) Support Ends-free Alignment.

	4) Optimize the Phil Green, Miller-Myers code borrowed from
	ssearch. Currently, it is doing many things that is only
	necessary in the sseach environment.

	5) For DNA sequences, provides an option to run reverse 
	complement search.

	6) Support six frames alignment between a DNA sequence and
	a protein sequence.

AUTHOR
	This implementation was written by Yee Man Chan (ymc at yahoo.com).
	Copyright (c) 2003 Yee Man Chan. All rights reserved. This program
	is free software; you can redistribute it and/or modify it under
	the same terms as Perl itself. Special thanks to Aaron Mackey
	and WIlliam Pearson for the helpful discussions. [The portion
	of code inside pgreen subdirectory was borrowed from ssearch. It
	should be distributed in the same terms as ssearch.]

SEE ALSO
	perl(1), m4(1)


On Tue, 20 May 2003, Aaron J Mackey wrote:

> 
> I'd say yes, but I don't want to hold anyone up.  Better probably to air
> this out in the public, so that anyone can jump in.
> 
> What's our status with Bio::Matrix for similarity matrices and/or
> profiles?  Yee, can you post some sample "SYNOPSIS"-type perl code that
> shows how one would use your stuff from "bioperl-space".
> 
> Thanks,
> 
> -Aaron
> 
> On Tue, 20 May 2003, Ewan Birney wrote:
> 
> >
> >
> > >
> > > 	I think my code is now worthy to be included in bioperl. Can you
> > > tell me how I can go about doing it?
> > >
> >
> > Someone needs to look at how well it binds to bioperl objects in terms of
> > bioperl-ext - probably that is either Aaron or me. Aaron - do you have
> > time to look at this or should I do this?
> >
> >
> >
> > > Thanks a lot.
> > > Yee Man
> > >
> > >
> >
> > _______________________________________________
> > Bioperl-l mailing list
> > Bioperl-l at portal.open-bio.org
> > http://portal.open-bio.org/mailman/listinfo/bioperl-l
> >
> 
> -- 
>  Aaron J Mackey
>  Pearson Laboratory
>  University of Virginia
>  (434) 924-2821
>  amackey at virginia.edu
> 
>