Morgan

MORGAN is an integrated system for finding genes in vertebrate DNA sequences. MORGAN uses a variety of techniques to accomplish this task, the most distinctive of which is a decision tree classifier. The decision tree system is combined with new methods for identifying start codons, donor sites, and acceptor sites, and these are brought together in a frame-sensitive dynamic programming algorithm that finds the optimal segmentation of a DNA sequence into coding and noncoding regions (exons and introns). The optimal segmentation is dependent on a separate scoring function that takes a subsequence and assigns to it a score reflecting the probability that the sequence is an exon. The scoring functions in MORGAN are sets of decision trees that are combined to give a probability estimate. Experimental results on a database of 570 vertebrate DNA sequences show that MORGAN has excellent performance by many different measures. The framework of our system is a dynamic programming algorithm that can efficiently consider the large number of alternative parses that are possible for any sequence of DNA. The dynamic programming algorithm guarantees that MORGAN will find the parse with the optimal score. The algorithm is computationally expensive, requiring time that is quadratic in the number of potential start, donor, and acceptor sites that MORGAN considers in a sequence. MORGAN's modularity allows us to filter these.

Inventor(s): Fasman, Kenneth H.

Type of Offer: Licensing



« More Software Patents

---