[algorithm] Help understanding substring chaining for spliced gene alignment

[gumbit]

Hi, I'm a newbie trying to understand the algorithm to align a spliced gene (lots of exons surrounded by introns) to a known gene.

My full question is posted here, and I think it would be bad form to copy paste it.

I'd be happy to just chat about various alignment algorithms too!

[shi]

Dear gumbit,

The Subjunc aligner goes some way similar to the substring chaining technique to map exon-spanning reads. It uses a number of 16bp subreads extracted from the read to probe the exon regions in the reference genome and to divide an exon-spanning read to multiple exonic blocks. It then confirms the discovered exon-exon junctions by checking the splicing signals and by re-aligning the putative exon-spanning reads.

For details, have a look at this paper - http://www.ncbi.nlm.nih.gov/pubmed/23558742


Best regards,

Wei

[gumbit]

Thank you very much, I'm reading it now.

Also in the Jones book it mentions that to perform this algorithm it generates a 3d array.
Is this similar to multiple local alignment?

[shi]

Hi gumbit,

Sorry, I dont know why you mean "3d array". Could you please elaborate it a bit?

Thanks,
Wei

[gumbit]

Sure, I think that in the algorithm it iterates over all the positions in string A, string B, and the list of "blocks" (blocks of exons that match between A and B), and the the final returned list of blocks has something to do with all 3 coordinates...
This is the paper on it: http://www.pnas.org/content/93/17/9061.full.pdf

[shi]

Note that Subjunc does not perform exon assembly that seems to be the aim of the paper you referred to.

Subjunc gives you the exon-exon junctions, not gene or transcript models. It uses those exon-spanning reads to discover the junctions and it does so by making use of the mappable regions in each read. The 16bp subreads extracted from the read are used to find these mappable regions. Subreads from the same block of the mappable region are virtually chained together to yield an exonic region. The discovered exonic regions are then used to find exon-exon junctions.

I hope this clarifies things.

Cheers,
Wei