Motif Discovery Algorithms
Various solutions have been proposed for the challenging problem of motif discovery. These algorithms can be classified under various paradigms such as exact counting methods, sampling methods, pattern growth methods and so on. However, motif discovery problem comprises two main steps: first, calculating the number of occurrences of a sub-graph and then, evaluating the sub-graph significance. The recurrence is significant if it is detectably far more than expected. Roughly speaking, the expected number of appearances of a sub-graph can be determined by a Null-model, which is defined by an ensemble of random networks with some of the same properties as the original network.
Here, a review on computational aspects of major algorithms is given and their related benefits and drawbacks from an algorithmic perspective are discussed.
Read more about this topic: Network Motif
Famous quotes containing the word discovery:
“He is not a true man of science who does not bring some sympathy to his studies, and expect to learn something by behavior as well as by application. It is childish to rest in the discovery of mere coincidences, or of partial and extraneous laws. The study of geometry is a petty and idle exercise of the mind, if it is applied to no larger system than the starry one.”
—Henry David Thoreau (1817–1862)