This is a test version of Biostars. For the public version, visit https://www.biostars.org.
Wanted: Basic Sequence Comparison Algorithm With Statistical Significance Output

In my dataset I have fragments ranging from 5 amino acids to 20 amino acids. For each lenght, I have 200,000 -- 400,000 distinct sequences.

I want to compare same-length sequence fragments (all vs. all) with no gaps allowed. Thus even Needleman-Wunsch is overkill because I don't need any alignment, just comparison. I know I could implement this myself with just one for-loop and a method to access the PAM/BLOSUM matrices. I did this already, actually.

My problem is that I want the values for different-length fragments to be comparable. If I just sum up the log-odds values of the substitution matrices, they are not. I need some statistical significance value like BLAST's E-value. But I don't know how to determine K and lamda for my database.

Isn't there something off-the-shelf I can use?

sequence
• 2,890 views • link
updated by Gustavo Gustavo • written by Fabian • Fabian

2 answers

Perhaps GGSEARCH from the FASTA package, setting the gap opening penalty to a sufficiently large value.

• 0 views • link
written by Gustavo Gustavo

Hi Gustavo, my problem is that I need this to be quite fast because I have so many sequences all vs. all. The whole NW dynamic programming stuff is unnecessary overhead.

• 0 views • link
written by Fabian • Fabian

Can this be of any help ?

Estimation of P-values for global alignments of protein sequences

http://www.ncbi.nlm.nih.gov/pubmed/11751224

• 0 views • link
written by Woa Woa

Log in to answer this question.

More posts like this