[BiO BB] Some questions of alignment

Evgeny Cheremushkin cheremushkin at ngs.ru
Fri Jun 18 23:02:15 EDT 2004

Hello Yuanji,

Saturday, June 19, 2004, 1:03:54 AM, you wrote:

ZY> Hello Dear Colleagues,

ZY> I have 2 mathmatical questions about necleotide sequence alignment:

ZY> 1. Given 2 homologous sequences of the same length (L) (e.g., L = 30 nt),
ZY> and mismatches (M, 0 <= M <= L) are allowed in the alignment, how many
ZY> possible alignments will be? (One assumption: biologically it does not make
ZY> much sense when M = L, but mathmatically, there is one possible alignment
ZY> between the 2 sequences, and mismatch occurs in every position.) 

If alignment is defined as all possible match-mismatch combinations,
then there are N=2^L possible alignments.

ZY> 2. Suppose blastn is used to detect the alignment. Given word size = 7,
ZY> mismatch punishment = -1, and match reward = 1, how many alignments cannot
ZY> be detected by blast?
As I understand: alignment is detected by blastn if L-M>0.
Have to be less then 4 matches.
undetected alignments number U=C(7,3)+C(7,2)+C(7,1)+1=64

ZY> Any idea is welcome.

ZY> _______________________________________________
ZY> BiO_Bulletin_Board maillist  - 
ZY> BiO_Bulletin_Board at bioinformatics.org
ZY> https://bioinformatics.org/mailman/listinfo/bio_bulletin_board

Best regards,
 Evgeny                            mailto:cheremushkin at ngs.ru

More information about the BBB mailing list