Description:

Given one exon, the main goal is to find the best gene finished in that exon (dynamic programming), looking for every exon which may be placed before it, according to the assembling rules expressed in the gene model, and selecting the best one (higher gene score). Given a rule or gene class, the set of exons that may be used at the left part of the rule are stored, sorted by donor (right) position, in the d-array structure (plus extra array of counters). This module sorts by donor the input exons according to every class rules and the type of exons. As the set of input exons were initially ordered by acceptor, donor re-arrangements are very similar and preserves quite well the original order.

Briefing:

void BuildSort(dict* D, int nc[], int ne[], int UC[][MAXENTRY], int DE[][MAXENTRY], int nclass, long km[], exonGFF* **d, exonGFF* E, long nexons)

Essentially, for every exon and the set of available rules or classes (in which its type is at the left part): to insert into the sorting function by running the sorting algorithm by insertion. (Note: As input exons are sorted by acceptor and this order is partially maintained in the arrangement by donor, there will be many simple insertion operations and few operations of shifting in the d-arrays (linear time cost)).

Enrique Blanco Garcia © 2001