en>BG19bot: /* Definition and calculation */WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - using AWB (9876)

2014-01-21T07:35:44Z

Definition and calculation: WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - using AWB (9876)

New page

The emergence and need for the analysis of different types of data generated through biological research has given rise to the field of [[Bioinformatics]].<ref>{{cite journal|last=Rothberg|first=J|coauthors=Merriman, B; Higgs, G|title=Bioinformatics. Introduction|journal=The Yale journal of biology and medicine|date=September 2012|volume=85|issue=3|pages=305–8|pmid=23189382|pmc=3447194}}</ref> Molecular sequence and structure data of [[DNA]], [[RNA]] and [[proteins]], [[gene expression]] profiles or [[micro array]] data, [[metabolic pathway]] data are some of the major types of data being analysed in Bioinformatics. Among them sequence data is increasing at the exponential rate due to advent of next-generation sequencing technologies. Since the origin of Bioinformatics [[sequence analysis]] has remained the major area of research with wide range of applications in Database searching, [[Genome annotation]], [[Comparative genomics]], [[Molecular phylogeny]], [[Gene prediction]] etc. The pioneering approaches for sequence analysis were based on [[sequence alignment]] either global or local, pairwise or [[multiple sequence alignment]].<ref>{{cite journal|last=Batzoglou|first=S|title=The many faces of sequence alignment|journal=Briefings in bioinformatics|date=March 2005|volume=6|issue=1|pages=6–22|pmid=15826353|doi=10.1093/bib/6.1.6}}</ref><ref>{{cite journal|last=Mullan|first=L|title=Pairwise sequence alignment--it's all about us!|journal=Briefings in bioinformatics|date=March 2006|volume=7|issue=1|pages=113–5|pmid=16761368|doi=10.1093/bib/bbk008}}</ref> Alignment-based approaches generally give excellent results when the sequences under study are closely related and can be reliably aligned, but when the sequences are divergent, a reliable alignment cannot be obtained and hence the applications of sequence alignment are limited. Another limitation of alignment-based approaches is their computational complexity and are time-consuming and thus, are limited when dealing with large-scale sequence data.<ref>{{cite journal|last=Kemena|first=C|coauthors=Notredame, C|title=Upcoming challenges for multiple sequence alignment methods in the high-throughput era|journal=Bioinformatics (Oxford, England)|date=Oct 1, 2009|volume=25|issue=19|pages=2455–65|pmid=19648142|doi=10.1093/bioinformatics/btp452|pmc=2752613}}</ref> The advent of [[next generation sequencing]] technologies has resulted in generation of voluminous sequencing data. The size of this sequence data poses challenges on alignment-based algorithms in their assembly, annotation and comparative studies. Thus, '''alignment-free sequence analysis''' approaches provide attractive alternatives over alignment-based approaches.<ref>{{cite journal|last=Vinga|first=S|coauthors=Almeida, J|title=Alignment-free sequence comparison-a review.|journal=Bioinformatics (Oxford, England)|date=Mar 1, 2003|volume=19|issue=4|pages=513–23|pmid=12611807}}</ref>

== Alignment-free methods ==
Alignment-free methods can broadly be classified into four categories, a) methods based on k-mer/word frequency, b) methods based on substrings, c) methods based on information theory and d) methods based on graphical representation. Alignment-free methods have mostly been tested for their applicability in molecular phylogeny analysis and compared against the classical alignment based approaches for phylogeny. The results of phylogeny reconstructed using alignment-free methods are not affected by sequence rearrangements <ref name="Ragan">{{cite journal|last=Chan|first=CX|coauthors=Ragan, MA|title=Next-generation phylogenomics.|journal=Biology direct|date=Jan 22, 2013|volume=8|pages=3|pmid=23339707}}</ref> see '''Figure 1'''.

[[File:Alignment based and alignment-free phylogeny.png|550px|thumbnail|right|Figure 1: Phylogenetic inference using alignment-based and alignment-free methods]]
Such molecular phylogeny analyses employing alignment-free approaches are said to be part of "next-generation phylogenomics".<ref name=Ragan />

=== Methods based on k-mer/word frequency ===
The popular methods based on k-mer/word frequencies include Feature Frequency Profile (FFP),<ref name="FFP">{{cite journal|last=Sims|first=GE|coauthors=Jun, SR; Wu, GA; Kim, SH|title=Whole-genome phylogeny of mammals: evolutionary information in genic and nongenic regions.|journal=Proceedings of the National Academy of Sciences of the United States of America|date=Oct 6, 2009|volume=106|issue=40|pages=17077–82|pmid=19805074}}</ref><ref>{{cite journal|last=Sims|first=GE|coauthors=Kim, SH|title=Whole-genome phylogeny of Escherichia coli/Shigella group by feature frequency profiles (FFPs).|journal=Proceedings of the National Academy of Sciences of the United States of America|date=May 17, 2011|volume=108|issue=20|pages=8329–34|pmid=21536867}}</ref> Composition vector (CV),<ref>{{cite journal|last=Gao|first=L|coauthors=Qi, J|title=Whole genome molecular phylogeny of large dsDNA viruses using composition vector method.|journal=BMC evolutionary biology|date=Mar 15, 2007|volume=7|pages=41|pmid=17359548}}</ref><ref>{{cite journal|last=Wang|first=H|coauthors=Xu, Z; Gao, L; Hao, B|title=A fungal phylogeny based on 82 complete genomes using the composition vector method.|journal=BMC evolutionary biology|date=Aug 10, 2009|volume=9|pages=195|pmid=19664262}}</ref> Return time distribution (RTD)<ref name="RTD1">{{cite journal|last=Kolekar|first=P|coauthors=Kale, M; Kulkarni-Kale, U|title=Alignment-free distance measure based on return time distribution for sequence analysis: applications to clustering, molecular phylogeny and subtyping.|journal=Molecular phylogenetics and evolution|date=November 2012|volume=65|issue=2|pages=510–22|pmid=22820020}}</ref><ref name="RTD2">{{cite journal|last=Kolekar|first=PS|coauthors=Kale, M; Kulkarni-Kale, U|title=Genotyping of Mumps viruses based on SH gene: Development of a server using alignment-free and alignment-based methods.|journal=Immunome research|date=Nov 30, 2011|volume=7|issue=3|pages=1–7|pmid=22126822}}</ref> and frequency chaos game representation (FCGR).<ref>{{cite journal|last=Hatje|first=K|coauthors=Kollmar, M|title=A phylogenetic analysis of the brassicales clade based on an alignment-free sequence comparison method.|journal=Frontiers in plant science|year=2012|volume=3|pages=192|pmid=22952468}}</ref>

==== Feature frequency profile (FFP) ====
The methodology involved in FFP based method starts by calculating the count of each possible k-mer (possible number of k-mers for nucleotide sequence: 4k, while that for protein sequence: 20k) in sequences. Each k-mer count in each sequence is then normalized by dividing it by total of all k-mers' count in that sequence. This leads to conversion of each sequence into its feature frequency profile. The pair wise distance between two sequences is then calculated [[Jensen-Shannon divergence|Jensen-Shannon (JS) divergence]] between their respective FFPs. The [[distance matrix]] thus obtained can be used to construct [[phylogenetic tree]] using clustering algorithms like [[Neighbor-joining]], [[UPGMA]] etc.

==== Composition vector (CV) ====
In this method frequency of appearance of each possible k-mer in a given sequence is calculated. The next characteristic step of this method is the subtraction of random background of these frequencies using [[Markov model]] to reduce the inﬂuence of random neutral [[mutations]] to highlight the role of selective evolution. The normalized frequencies are put a ﬁxed order to form the composition vector (CV) of a given sequence. [[Cosine distance]] function is then used to compute pairwise distance between CVs of sequences. The distance matrix thus obtained can be used to construct phylogenetic tree using clustering algorithms like [[Neighbor-joining]], [[UPGMA]] etc. This method can be extended through resort to efficient pattern matching algorithms to include in the computation of the composition vectors: (i) all k-mers for any value of k, (ii) all substrings of any length up
to an arbitrarily set maximum k value, (iii) all maximal substrings, where a substring is maximal if extending it by any character would cause a decrease in its occurrence count
<ref>{{cite journal|last=Apostolico|first=A|coauthors=Denas, O |title=Fast algorithms for computing sequence distances by exhaustive substring composition.|journal=Algorithms for Molecular Biology|date=March 2008|volume=3}}</ref><ref>{{cite journal|last=Apostolico|first=A|coauthors=Denas, O; Dress, A |title=Efficient tools for comparative substring analysis.|journal= Journal of Biotechnology|date=September 2010|volume=149|issue=3|pages=120–126}}</ref>.

==== Whole Substring Composition ====

==== Return time distribution (RTD) ====
The RTD based method does not calculate the count of k-mers in sequences, instead it computes the time required for the reappearance of
k-mers. The time refers to the number of residues in successive appearance of particular k-mer. Thus the occurrence of each k-mer in a sequence is calculated in the form of RTD, which is then summarised using two statistical parameters [[mean]] (�μ) and [[standard deviation]] (σ�). Thus each sequence is represented in the form of numeric vector of size 2*4k containing �μ and σ of 4k RTDs. The pair wise distance between sequences is calculated using [[Euclidean distance]] measure. The distance matrix thus obtained can be used to construct phylogenetic tree using clustering algorithms like [[Neighbor-joining]], [[UPGMA]] etc.

==== Frequency chaos game representation (FCGR) ====
The FCGR methods have evolved from Chaos game representation (CGR) technique, which provides scale independent representation for genomic sequences.<ref>{{cite journal|last=Jeffrey|first=HJ|title=Chaos game representation of gene structure.|journal=Nucleic acids research|date=Apr 25, 1990|volume=18|issue=8|pages=2163–70|pmid=2336393}}</ref> The CGRs can be divided by grid lines where each grid square denotes the occurrence of oligonucleotides of a specific length in the sequence. Such representation of CGRs is termed as Frequency Chaos Game Representation (FCGR). This leads to representation of each sequence into FCGR. The pair wise distance between FCGRs of sequences can be calculated using either the Pearson distance or the Euclidean distance.<ref>{{cite journal|last=Wang|first=Y|coauthors=Hill, K; Singh, S; Kari, L|title=The spectrum of genomic signatures: from dinucleotides to chaos game representation.|journal=Gene|date=Feb 14, 2005|volume=346|pages=173–85|pmid=15716010}}</ref>

=== Methods based on substrings ===

The methods in this category employ the similarity and differences of substrings in a pair of sequences. These algorithms
were mostly used for string processing in [[computer science]].<ref>{{cite book|last=Gusfield|first=Dan|title=Algorithms on strings, trees, and sequences : computer science and computational biology|year=1997|publisher=Cambridge Univ. Press|location=Cambridge [u.a.]|isbn=9780521585194|edition=Reprinted (with corr.)}}</ref>

==== Average common substring (ACS) ====

In this approach, for a chosen pair of sequences (A and B of lengths l and m respectively), longest substring starting at some position is identified in one sequence (A) which exactly matches in the other sequence (B) at any position. All these lengths are averaged to derive a measure <math>L(A, B)</math>. Intuitively, larger the <math>L(A, B)</math>, the more similar the two sequences are. To account for the differences in the length of sequences, <math>L(A, B)</math> is normalized [i.e. <math>L(A, B)/\log(m)</math>]. This gives the similarity measure between the sequences.

In order to derive a distance measure, the inverse of similarity measure is taken and a correction term is subtracted from it to assure that <math>d(A, A)</math> will be zero.

Thus, <math>d(A, B) = [\log(m)/L(A, B)] - [\log(n)/L(A, A]</math>.

This measure <math>d(A, B)</math> is not symmetric, so one has to compute <math>d_s(A, B) = d_s(B, A) = (d(A, B) + d(B, A))/2</math>, which gives ﬁnal ACS measure between the two strings (A and B).<ref>{{cite journal|last=Ulitsky|first=I|coauthors=Burstein, D; Tuller, T; Chor, B|title=The average common substring approach to phylogenomic reconstruction.|journal=Journal of computational biology : a journal of computational molecular cell biology|date=March 2006|volume=13|issue=2|pages=336–50|pmid=16597244}}</ref> The subsequence/substring search can be efficiently performed by
using [[Suffix tree|sufﬁx trees]].<ref>{{cite web|last=Weiner|first=P|title=Linear pattern matching algorithms|url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4569722|work=IEEE}}</ref><ref>{{cite journal|last=He|first=D|title=Using suffix tree to discover complex repetitive patterns in DNA sequences.|journal=Conference proceedings : ... Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Conference|year=2006|volume=1|pages=3474–7|pmid=17945779}}</ref><ref>{{cite journal|last=Välimäki|first=N|coauthors=Gerlach, W; Dixit, K; Mäkinen, V|title=Compressed suffix tree--a basis for genome-scale sequence analysis.|journal=Bioinformatics (Oxford, England)|date=Mar 1, 2007|volume=23|issue=5|pages=629–30|pmid=17237063}}</ref>

==== Mutation distances (Kr) ====

This approach is closely related to the ACS, which calculates the number of substitutions per site between two DNA sequences using the shortest
absent substring (termed as shustring).<ref>{{cite journal|last=Haubold|first=B|coauthors=Pfaffelhuber, P; Domazet-Loso, M; Wiehe, T|title=Estimating mutation distances from unaligned genomes.|journal=Journal of computational biology : a journal of computational molecular cell biology|date=October 2009|volume=16|issue=10|pages=1487–500|pmid=19803738}}</ref>

=== Methods based on Information theory ===

Information Theory has provided successful methods for alignment-free sequence analysis and comparison. The existing applications of information theory include global and local characterization of DNA, RNA and proteins, estimating genome entropy to motif and region classification. It also holds promise in gene mapping, next-generation sequencing analysis and metagenomics.<ref>{{cite journal|last=Vinga|first=S|title=Information theory applications for biological sequence analysis.|journal=Briefings in bioinformatics|date=Sep 20, 2013|pmid=24058049}}</ref>

==== Base base correlation (BBC) ====

Base base correlation (BBC)converts the genome sequence into a unique 16-dimensional numeric vector using the following equation, 
<math>T_{ij}(K) = \sum_{l=1}^K P_{ij}(l).\log_{2} \left ( \frac{P_{ij}(l)}{P_{i}P_{j}} \right )</math> 
The <math>P_{i}</math> and <math>P_{j}</math> denotes the probabilities of bases i and j in the genome. The <math>P_{ij}(l)</math> indicates the probability of bases i and j at distance l in the genome. The parameter K indicates the maximum distance between the bases i and j. The variation in the values of 16 parameters reflect variation in the genome content and length.<ref>{{cite journal|last=Liu|first=Z|coauthors=Meng, J; Sun, X|title=A novel feature-based method for whole genome phylogenetic analysis without alignment: application to HEV genotyping and subtyping.|journal=Biochemical and biophysical research communications|date=Apr 4, 2008|volume=368|issue=2|pages=223–30|pmid=18230342}}</ref><ref>{{cite journal|last=Liu|first=ZH|coauthors=Sun, X|title=Coronavirus phylogeny based on base-base correlation.|journal=International journal of bioinformatics research and applications|year=2008|volume=4|issue=2|pages=211–20|pmid=18490264}}</ref><ref>{{cite journal|last=Cheng|first=J|coauthors=Zeng, X; Ren, G; Liu, Z|title=CGAP: a new comprehensive platform for the comparative analysis of chloroplast genomes.|journal=BMC bioinformatics|date=Mar 14, 2013|volume=14|pages=95|pmid=23496817}}</ref>

==== Information correlation and partial information correlation (IC-PIC) ====
IC-PIC (information correlation and partial information correlation) based method employs the base correlation property of DNA sequence. IC and PIC were calculated using following formulas,

<math> IC_l = -2 \sum_{i} p_i \log_2 p_i + \sum_{ij} p_{ij} (l) \log_2 p_{ij} (l)</math>

<math> PIC_{ij} (l) = (p_{ij} (l) - P_i P_j (l))^2</math>

The final vector is obtained as following,

<math>V = {IC_l \over PIC_{ij} (l)} </math> here <math> l \isin \left \{ l_0, l_0 + 1, ..., l_0 + n \right \} </math> which defines the range of distance between bases.<ref>{{cite journal|last=Gao|first=Y|coauthors=Luo, L|title=Genome-based phylogeny of dsDNA viruses by a novel alignment-free method.|journal=Gene|date=2012 Jan 15|volume=492|issue=1|pages=309–14|pmid=22100880}}</ref>

The pair wise distance between sequences is calculated using Euclidean distance measure. The distance matrix thus obtained can be used to construct phylogenetic tree using clustering algorithms like Neighbor-joining, UPGMA etc.

==== Lempel-Ziv compress ====
Lempel-Ziv complexity uses the relative information between the sequences. This complexity is measured by the number of steps required to generate a string given the prior knowledge of another string and a self-delimiting production process. This measure has a relation to measuring k-words in a sequence, as they can be easily used to generate the sequence. It is computational intensive method. Otu and Sayood (2003) used this method to construct five different distance measures for phylogenetic tree construction.<ref>{{cite journal|last=Otu|first=HH|coauthors=Sayood, K|title=A new sequence distance measure for phylogenetic tree construction.|journal=Bioinformatics (Oxford, England)|date=2003 Nov 1|volume=19|issue=16|pages=2122–30|pmid=14594718}}</ref>

=== Methods based on graphical representation ===

==== Iterated Maps ====
The use of iterated maps for sequence analysis was first introduced by HJ Jefferey in 1990<ref>{{cite journal|last=Jeffrey|first=HJ|title=Chaos game representation of gene structure.|journal=Nucleic acids research|date=Apr 25, 1990|volume=18|issue=8|pages=2163–70|pmid=2336393}}</ref> when he proposed to apply the [[Chaos game|Chaos Game]] to map genomic sequences into a unit square. That report coined the procedure as Chaos Game Representation (CGR). However, only 3 years later this approach was first dismissed as a projection of a Markov transition table by N Goldman.<ref>{{cite journal|last=Goldman|first=N|title=Nucleotide, dinucleotide and trinucleotide frequencies explain patterns observed in chaos game representations of DNA sequences.|journal=Nucleic acids research|date=May 25, 1993|volume=21|issue=10|pages=2487–91|pmid=8506142}}</ref> This objection was overruled by the end of that decade when the opposite was found to be the case - that CGR bijectively maps Markov transition is into a fractal, order-free (degree-free) representation.<ref>{{cite journal|last=Almeida|first=JS|coauthors=Carriço, JA; Maretzek, A; Noble, PA; Fletcher, M|title=Analysis of genomic sequences by Chaos Game Representation.|journal=Bioinformatics (Oxford, England)|date=May 2001|volume=17|issue=5|pages=429–37|pmid=11331237}}</ref> The realization that iterated maps provide a bijective map between the symbolic space and numeric space led to the identification of a variety of alignment-free approaches to sequence comparison and characterization. These developments were reviewed in late 2013 by JS Almeida in.<ref>{{cite journal|last=Almeida|first=JS|title=Sequence analysis by iterated maps, a review.|journal=Briefings in bioinformatics|date=Oct 25, 2013|pmid=24162172}}</ref> A number of web apps such as http://usm.github.com are available to demonstrate how to encode and compare arbitrary symbolic sequences.

== Comparison of alignment based and alignment-free methods <ref name=Ragan /> ==
{| class="wikitable"
|-
! Alignment-based methods !! Alignment-free methods
|-
| These methods assume that homologous regions are contiguous (with gaps) || Does not assume such contiguity of homologous regions
|-
| Computes all possible pairwise comparisons of sequences; hence computationally expensive || Based on occurrences of sub-sequences; composition; computationally inexpensive, can be memory-intensive
|-
| Well-established approach in phylogenomics || Relatively recent and application in phylogenomics is limited; needs further testing for robustness and scalability
|-
| Requires substitution/evolutionary models || Less dependent on substitution/evolutionary models
|-
| Sensitive to stochastic sequence variation, recombination, horizontal genetic transfer, rate heterogeneity and sequences of varied lengths, especially when similarity lies in the “twilight zone” || Less sensitive to stochastic sequence variation, recombination, horizonatal genetic transfer, rate heterogeneity and sequences of varied lengths
|-
| Best practice uses inference algorithms with complexity at least O(n2); less time-efficient || Inference algorithms typically O(n2) or less; more time-efficient
|-
| Heuristic in nature; statistical significance of how alignment scores relate to homology is difficult to assess || Exact solutions; statistical significance of the sequence distances (and degree of similarity) can be readily assessed
|}

== Applications of alignment-free methods ==
* Molecular phylogenetics<ref name=Ragan />
* Metagenomics<ref name="NGS">{{cite journal|last=Song|first=K|coauthors=Ren, J; Reinert, G; Deng, M; Waterman, MS; Sun, F|title=New developments of alignment-free sequence comparison: measures, statistics and next-generation sequencing.|journal=Briefings in bioinformatics|date=2013 Nov 26|pmid=24064230}}</ref>
* Next generation sequence data analysis<ref name=NGS />
* Epigenomics<ref>{{cite journal|last=Pinello|first=L|coauthors=Lo Bosco, G; Yuan, GC|title=Applications of alignment-free methods in epigenomics.|journal=Briefings in bioinformatics|date=2013 Nov 6|pmid=24197932}}</ref>
* Barcoding of species<ref>{{cite journal|last=La Rosa|first=M|coauthors=Fiannaca, A; Rizzo, R; Urso, A|title=Alignment-free analysis of barcode sequences by means of compression-based methods.|journal=BMC bioinformatics|date=2013|volume=14 Suppl 7|pages=S4|pmid=23815444}}</ref>
* Population genetics<ref>{{cite journal|last=Haubold|first=B|title=Alignment-free phylogenetics and population genetics.|journal=Briefings in bioinformatics|date=2013 Nov 29|pmid=24291823}}</ref>
* Horizontal gene transfer<ref>{{cite journal|last=Domazet-Lošo|first=M|coauthors=Haubold, B|title=Alignment-free detection of local similarity among viral and bacterial genomes.|journal=Bioinformatics (Oxford, England)|date=2011 Jun 1|volume=27|issue=11|pages=1466-72|pmid=21471011}}</ref>
* Sero/genotyping of viruses<ref name="RTD3">{{cite journal|last=Kolekar|first=P|coauthors=Hake, N; Kale, M; Kulkarni-Kale, U|title=WNV Typer: A server for genotyping of West Nile viruses using an alignment-free method based on a return time distribution.|journal=Journal of virological methods|date=2013 Dec 31|pmid=24388930}}</ref><ref name=RTD1 /> <ref name=RTD2 />
* Allergenicity prediction<ref name="AllergenFP">{{cite journal|last=Dimitrov|first=I|coauthors=Naneva, L; Doytchinova, I; Bangov, I|title=AllergenFP: allergenicity prediction by descriptor fingerprints.|journal=Bioinformatics (Oxford, England)|date=2013 Nov 7|pmid=24167156}}</ref>
* SNP discovery<ref name="SNP">{{cite journal|last=Gardner|first=SN|coauthors=Hall, BG|title=When Whole-Genome Alignments Just Won't Work: kSNP v2 Software for Alignment-Free SNP Discovery and Phylogenetics of Hundreds of Microbial Genomes.|journal=PloS one|date=2013 Dec 9|volume=8|issue=12|pages=e81760|pmid=24349125}}</ref>
* Recombination detection<ref name="rush">{{cite journal|last=Haubold|first=B|coauthors=Krause, L; Horn, T; Pfaffelhuber, P|title=An alignment-free test for recombination.|journal=Bioinformatics (Oxford, England)|date=2013 Dec 15|volume=29|issue=24|pages=3121-7|pmid=24064419}}</ref>

== List of web servers/software for alignment-free methods ==
{| class="wikitable"
|-
! Name !! Description !! Availability !! Reference
|-
| FFP || Feature frequency profile based phylogeny || [http://sourceforge.net/projects/ffp-phylogeny/ FFP] || <ref name=FFP />
|-
| CVTree || Composition vector based server for phylogeny|| [http://tlife.fudan.edu.cn/cvtree/ CVTree] || <ref>{{cite journal|last=Xu|first=Z|coauthors=Hao, B|title=CVTree update: a newly designed phylogenetic study platform using composition vectors and whole genomes.|journal=Nucleic acids research|date=2009 Jul|volume=37|issue=Web Server issue|pages=W174-8|pmid=19398429}}</ref>
|-
| RTD Phylogeny || Return time distribution based server for phylogeny|| [http://bioinfo.net.in/RTD/home.html RTD Phylogeny] || <ref name=RTD1 />
|-
| AGP || A multimethods web server for alignment-free genome phylogeny || [http://www.herbbol.org:8000/agp AGP] || <ref>{{cite journal|last=Cheng|first=J|coauthors=Cao, F; Liu, Z|title=AGP: a multimethods web server for alignment-free genome phylogeny.|journal=Molecular biology and evolution|date=2013 May|volume=30|issue=5|pages=1032-7|pmid=23389766}}</ref>
|-
| Alfy || Alignment-free detection of local similarity among viral and bacterial genomes || [http://guanine.evolbio.mpg.de/alfy/ Alfy] || <ref>{{cite journal|last=Domazet-Lošo|first=M|coauthors=Haubold, B|title=Alignment-free detection of local similarity among viral and bacterial genomes.|journal=Bioinformatics (Oxford, England)|date=2011 Jun 1|volume=27|issue=11|pages=1466-72|pmid=21471011}}</ref>
|-
| decaf+py || DistancE Calculation using Alignment-Free methods in PYthon || [http://acb.qfab.org/acb/decaf+py/ decaf+py] || <ref>{{cite journal|last=Höhl|first=M|coauthors=Rigoutsos, I; Ragan, MA|title=Pattern-based phylogenetic distance estimation and tree reconstruction.|journal=Evolutionary bioinformatics online|date=2007 Feb 25|volume=2|pages=359-75|pmid=19455227}}</ref>
|-
| MuV genotyping server || Genotyping of Mumps viruses based on RTD || [http://117.239.43.117:1800/muv/homepage.html MuV Genotyping server] || <ref name=RTD2 />
|-
| Dengue Subtyper || Genotyping of Dengue viruses based on RTD || [http://117.239.43.117:1800/Dengue/homepage.html Dengue Subtyper] || <ref name=RTD1 />
|-
| WNV Typer || Genotyping of West nile viruses based on RTD || [http://117.239.43.117:1800/WNV/homepage.html WNV Typer] || <ref name=RTD3 />
|-
| AllergenFP || Allergenicity prediction by descriptor fingerprints || [http://ddg-pharmfac.net/AllergenFP/ AllergenFP] || <ref name=AllergenFP />
|-
| kSNP v2 || Alignment-Free SNP Discovery || [http://sourceforge.net/projects/ksnp/ kSNP v2] || <ref name=SNP />
|-
| d2Tools || Comparison of Metatranscriptomic Samples Based on k-Tuple Frequencies || [https://code.google.com/p/d2-tools/ d2Tools] || <ref>{{cite journal|last=Wang|first=Y|coauthors=Liu, L; Chen, L; Chen, T; Sun, F|title=Comparison of Metatranscriptomic Samples Based on k-Tuple Frequencies.|journal=PloS one|date=2014 Jan 2|volume=9|issue=1|pages=e84348|pmid=24392128}}</ref>
|-
| rush || Recombination detection Using SHustrings || [http://guanine.evolbio.mpg.de/rush/ rush] || <ref name=rush />
|}

== See also ==
*[[Sequence analysis]]
*[[Multiple sequence alignment]]
*[[Phylogenomics]]
*[[Bioinformatics]]
*[[Metagenomics]]
*[[Next-generation sequencing]]
*[[Population genetics]]
*[[SNPs]]
*[[Recombination detection program]]

== References ==

{{Reflist}}

[[Category:Bioinformatics]]
[[Category:Computational biology]]

Checkerboard score - Revision history

en>BG19bot: /* Definition and calculation */WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - using AWB (9876)