Editing Sequence motif (section)

===Overview===
The sequence motif discovery process has been well-developed since the 1990s. In particular, most of the existing motif discovery research focuses on DNA motifs. With the advances in high-throughput sequencing, such motif discovery problems are challenged by both the sequence pattern degeneracy issues and the data-intensive computational scalability issues.

'''Process of discovery'''
[[File:Sequence_Motif_Discovery.jpg|thumb|440x440px|A flowchart depicting the process of motif discovery]]
Motif discovery happens in three major phases. A pre-processing stage where sequences are meticulously prepared in assembly and cleaning steps. Assembly involves selecting sequences that contain the desired motif in large quantities, and extraction of unwanted sequences using clustering. Cleaning then ensures the removal of any confounding elements. Next there is the discovery stage. In this phase sequences are represented using consensus strings or [[Position weight matrix|Position-specific Weight Matrices (PWM)]]. After motif representation, an objective function is chosen and a suitable search algorithm is applied to uncover the motifs. Finally the post-processing stage involves evaluating the discovered motifs.<ref name="Avicenna 2019">{{Cite journal |last1=Hashim |first1=Fatma A. |last2=Mabrouk |first2=Mai S. |last3=Al-Atabany |first3=Walid |date=2019 |title=Review of Different Sequence Motif Finding Algorithms |journal=Avicenna Journal of Medical Biotechnology |volume=11 |issue=2 |pages=130–148 |issn=2008-2835 |pmc=6490410 |pmid=31057715}}</ref>

====''De novo'' motif discovery====
There are software programs which, given multiple input sequences, attempt to identify one or more candidate motifs. One example is the [[Multiple EM for Motif Elicitation]] (MEME) algorithm, which generates statistical information for each candidate.<ref name="Bailey2006">{{cite journal | vauthors = Bailey TL, Williams N, Misleh C, Li WW | title = MEME: discovering and analyzing DNA and protein sequence motifs | journal = Nucleic Acids Research | volume = 34 | issue = Web Server issue | pages = W369-73 | date = July 2006 | pmid = 16845028 | pmc = 1538909 | doi = 10.1093/nar/gkl198 }}</ref> There are more than 100 publications detailing motif discovery algorithms; Weirauch ''et al''. evaluated many related algorithms in a 2013 benchmark.<ref name="Weirauch2013">{{cite journal | vauthors = Weirauch MT, Cote A, Norel R, Annala M, Zhao Y, Riley TR, Saez-Rodriguez J, Cokelaer T, Vedenko A, Talukder S, Bussemaker HJ, Morris QD, Bulyk ML, Stolovitzky G, Hughes TR | display-authors = 6 | title = Evaluation of methods for modeling transcription factor sequence specificity | journal = Nature Biotechnology | volume = 31 | issue = 2 | pages = 126–34 | date = February 2013 | pmid = 23354101 | pmc = 3687085 | doi = 10.1038/nbt.2486 }}
</ref> The [[planted motif search]] is another motif discovery method that is based on combinatorial approach.

====Phylogenetic motif discovery====
Motifs have also been discovered by taking a [[phylogenetic]] approach and studying similar genes in different species. For example, by aligning the amino acid sequences specified by the GCM (''glial cells missing'') gene in man, mouse and ''D. melanogaster'', Akiyama and others discovered a pattern which they called the [[GCM transcription factors|GCM motif]] in 1996.<ref name="Akiyama1996">{{cite journal | vauthors = Akiyama Y, Hosoya T, Poole AM, Hotta Y | title = The gcm-motif: a novel DNA-binding motif conserved in Drosophila and mammals | journal = Proceedings of the National Academy of Sciences of the United States of America | volume = 93 | issue = 25 | pages = 14912–6 | date = December 1996 | pmid = 8962155 | pmc = 26236 | doi = 10.1073/pnas.93.25.14912 | bibcode = 1996PNAS...9314912A | doi-access = free }}</ref>  It spans about 150 amino acid residues, and begins as follows:

: <code>WDIND*.*P..*...D.F.*W***.**.IYS**...A.*H*S*WAMRNTNNHN</code>

Here each <code>.</code> signifies a single amino acid or a gap, and each <code>*</code> indicates one member of a closely related family of amino acids. The authors were able to show that the motif has DNA binding activity.

A similar approach is commonly used by modern [[protein domain]] databases such as [[Pfam]]: human curators would select a pool of sequences known to be related and use computer programs to align them and produce the motif profile (Pfam uses [[hidden Markov model|HMMs]], which can be used to identify other related proteins.<ref>{{cite web |title=Modelling in Pfam |url=https://www.ebi.ac.uk/training/online/courses/pfam-creating-protein-families/modelling-in-pfam/ |website=Pfam |access-date=14 December 2023 |language=en}}</ref> A phylogenic approach can also be used to enhance the ''de novo'' MEME algorithm, with PhyloGibbs being an example.<ref name="Siddharthan2005">{{cite journal | vauthors = Siddharthan R, Siggia ED, van Nimwegen E | title = PhyloGibbs: a Gibbs sampling motif finder that incorporates phylogeny | journal = PLOS Computational Biology | volume = 1 | issue = 7 | pages = e67 | date = December 2005 | pmid = 16477324 | pmc = 1309704 | doi = 10.1371/journal.pcbi.0010067 | bibcode = 2005PLSCB...1...67S | doi-access = free }}</ref>

====''De novo'' motif pair discovery====

In 2017, MotifHyades has been developed as a motif discovery tool that can be directly applied to paired sequences.<ref name="pmid28633280">{{cite journal | vauthors = Wong KC | title = MotifHyades: expectation maximization for de novo DNA motif pair discovery on paired sequences | journal = Bioinformatics | volume = 33 | issue = 19 | pages = 3028–3035 | date = October 2017 | pmid = 28633280 | doi = 10.1093/bioinformatics/btx381 | doi-access = free }}</ref>

====''De novo'' motif recognition from protein====

In 2018, a [[Markov random field]] approach has been proposed to infer DNA motifs from [[DNA-binding domains]] of proteins.<ref name="pmid30267681">{{cite journal | vauthors = Wong KC | title = DNA Motif Recognition Modeling from Protein Sequences | journal = iScience | volume = 7 | pages = 198–211 | date = September 2018 | pmid = 30267681 | pmc = 6153143 | doi = 10.1016/j.isci.2018.09.003 | bibcode = 2018iSci....7..198W }}</ref>

'''Motif Discovery Algorithms'''

Motif discovery algorithms use diverse strategies to uncover patterns in DNA sequences. Integrating enumerative, probabilistic, and nature-inspired approaches, demonstrate their adaptability, with the use of multiple methods proving effective in enhancing identification accuracy.

'''Enumerative Approach:'''<ref name="Avicenna 2019" />

Initiating the motif discovery journey, the enumerative approach witnesses algorithms meticulously generating and evaluating potential motifs. Pioneering this domain are Simple Word Enumeration techniques, such as YMF and DREME, which systematically go through the sequence in search of short motifs. Complementing these, Clustering-Based Methods such as CisFinder employ nucleotide substitution matrices for motif clustering, effectively mitigating redundancy. Concurrently, Tree-Based Methods like Weeder and FMotif exploit tree structures, and Graph Theoretic-Based Methods (e.g., WINNOWER) employ graph representations, demonstrating the richness of enumeration strategies.

'''Probabilistic Approach:'''<ref name="Avicenna 2019" />

Diverging into the probabilistic realm, this approach capitalizes on probability models to discern motifs within sequences. MEME, a deterministic exemplar, employs Expectation-Maximization for optimizing Position Weight Matrices (PWMs) and unraveling conserved regions in unaligned DNA sequences. Contrasting this, stochastic methodologies like Gibbs Sampling initiate motif discovery with random motif position assignments, iteratively refining the predictions. This probabilistic framework adeptly captures the inherent uncertainty associated with motif discovery.

'''Advanced Approach:'''<ref name="Avicenna 2019" />

Evolving further, advanced motif discovery embraces sophisticated techniques, with [[Bayesian modeling]]<ref>{{Cite journal |last1=Miller |first1=Andrew K. |last2=Print |first2=Cristin G. |last3=Nielsen |first3=Poul M. F. |last4=Crampin |first4=Edmund J. |date=2010-11-18 |title=A Bayesian search for transcriptional motifs |journal=PLOS ONE |volume=5 |issue=11 |pages=e13897 |doi=10.1371/journal.pone.0013897 |issn=1932-6203 |pmc=2987817 |pmid=21124986 |bibcode=2010PLoSO...513897M |doi-access=free }}</ref> taking center stage. LOGOS and BaMM, exemplifying this cohort, intricately weave Bayesian approaches and [[Markov model|Markov models]] into their fabric for motif identification. The incorporation of Bayesian clustering methods enhances the probabilistic foundation, providing a holistic framework for pattern recognition in DNA sequences.

'''Nature-Inspired and Heuristic Algorithms:'''<ref name="Avicenna 2019" />

A distinct category unfolds, wherein algorithms draw inspiration from the biological realm. [[Genetic algorithm|Genetic Algorithms (GA)]], epitomized by FMGA and MDGA,<ref>{{Cite book |last1=Che |first1=Dongsheng |last2=Song |first2=Yinglei |last3=Rasheed |first3=Khaled |chapter=MDGA: Motif discovery using a genetic algorithm |date=2005-06-25 |title=Proceedings of the 7th annual conference on Genetic and evolutionary computation |chapter-url=https://doi.org/10.1145/1068009.1068080 |series=GECCO '05 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=447–452 |doi=10.1145/1068009.1068080 |isbn=978-1-59593-010-1|s2cid=7892935 }}</ref> navigate motif search through genetic operators and specialized strategies. Harnessing swarm intelligence principles, [[Particle swarm optimization|Particle Swarm Optimization (PSO)]], [[Artificial bee colony algorithm|Artificial Bee Colony (ABC)]] algorithms, and [[Cuckoo search|Cuckoo Search (CS)]] algorithms, featured in GAEM, GARP, and MACS, venture into pheromone-based exploration. These algorithms, mirroring nature's adaptability and cooperative dynamics, serve as avant-garde strategies for motif identification. The synthesis of heuristic techniques in hybrid approaches underscores the adaptability of these algorithms in the intricate domain of motif discovery.
[[File:Sequence_motif_algorithm_figure.jpg|center|thumb|500x500px|This chart shows many different types of algorithms used in the discovery of sequence motifs and their categories]]