Flak 1.0 - Ultra-fast Fuzzy Whole-genome Alignment
Flak 1.0 - Ultra-fast Fuzzy Whole-genome Alignment   Download FLAK 1.0

 

Support FLAK!

 

Hedges & Fuzzy Operators

By utilising a fuzzy model to represent and compare DNA sequences, a range of fuzzy set and logical operations can be exploited by FLAK. Mathematically, fuzzy logic is a superset of bivalent boolean logic and, as a consequence, the logical operators used in boolean logic also have the same truth values in fuzzy logic. Fuzzy set operations are known as hedges and are used to strengthen or weaken set membership. In FLAK, these operations are applied to an alignment post hoc, using simple GUI controls, and can be used to identify areas of strong or weak homology. The result of a fuzzy operation is visualised and affects the output of alignment data. The operations described below are applied to the result of the μA(x) fuzzy set membership function returned by the Levenshtein distance algorithm and have the effect of modifying the shape of a fuzzy set. If the result of a fuzzy operation reduces the membership value of part of an alignment to <β, that alignment will no longer be visualised or outputted. All fuzzy operations in FLAK are revocable.

 

Hedges

Hedges are terms that modify the shape of a fuzzy set and act as operations that can concentrate or dilate a fuzzy set into a new fuzzy subset. Hedges can also be used to break down a continuum of fuzzy values into intervals. FLAK provides three hedges, described by the adverbs very, extremely and very very that concentrate the alignments in a fuzzy set. The hedge options are displayed in the toolbar on the plotter window:
Hedge Buttons

As illustrated in the diagram below (green line), the fuzzy set membership function, μA(x), maps edit distances to fuzzy values. Applying a very hedge (blue line) concentrates the fuzzy set to include only very similar alignments. The extremely hedge (red line) concentrates the fuzzy set even further, with the very very hedge (orange line) applying the maximum concentration to a set. These strong modifiers will reduce the fuzzy set membership value of alignments. Any alignments that fall below the β cut-off threshold will be discarded while the hedge is applied.

 

Hedges

 

Very Similar Alignments

Very is a concentration operation that narrows a set and reduces the degree of membership of fuzzy elements. The very operation is given as a mathematical square:

Very Hedge

A membership value of 0.8 (an edit distance of 6) in a fuzzy set similar will become 0.64 in the set of very similar.

 

Extremely Similar Alignments

Extremely is also a concentration operation and is given by the 3rd power of a membership value:

Extremely Hedge

A membership value of 0.8 in a fuzzy set similar will become 0.512 in the set of extremely similar.

 

Very Very Similar Alignments

Very very is an extension of the basic very concentration and is computed as the square of the operation of concentration:

Very Very Hedge

A membership value of 0.8 in similar will become 0.4096 in the set of very very similar. As this membership value is below the β cut-off threshold of 0.46, the alignment will not be displayed or outputted.

 

Fuzzy Operators

The logical operators (AND, OR and NOT) that are fundamental to boolean logic can also be used in fuzzy logic. These operations can be applied to a genome comparison using the toolbar options in the plotter window. Note that the visual impact of using these operations will depend on the homology between the query and reference genomes and the β cut-off threshold. Applying fuzzy operations to the results of an alignment of highly homologous sequences will not alter the visual representation of a genome comparison, as the strong homology will generate alignments with consistently high fuzzy membership values. Likewise, if the β cut-off threshold is set to values >0.7, the visual impact of fuzzy operations will be diminished.

Fuzzy AND

A logical AND operation is the intersection (∩) between two sets that contain shared elements. In fuzzy logic, this is expressed as:

Fuzzy AND

A fuzzy intersection is therefore the lower membership value in both sets of each element. FLAK implements AND by applying the selecting the smallest μA(x) membership value of a contiguous alignment of a query sequence against a reference genome.

 

Fuzzy OR

A logical OR can be implemented in fuzzy logic as the union (∪ ) of two fuzzy sets and consists of every element that belongs to either set. The union is the largest membership value of the element in either set and is expressed as:

Fuzzy OR

The logical OR implementation in FLAK selects the largest μA(x) membership value of a contiguous alignment of a query sequence against a reference genome.

 

Fuzzy NOT

The complement of a set is the logical NOT of a set and is expressed as:

Fuzzy OR

An alignment in FLAK with a μA(x) membership value of 0.8 will have a μ¬A(x) value of 0.2.

 

 

 

© 2016.  FLAK (Fuzzy Logic Analysis of k-mers) Version 1.0     
Flak 1.0 - Ultra-fast Fuzzy Whole-genome Alignment