Often, DNA fingerprinting deals with DNA sequences at the molecular level. Therefore, it is important to understand terminologies like locus, allele, polymorphism (and their different types) and tandem repeats. These are discussed in the following paragraphs.

The physical location (i.e. at the molecular level) in the genome is called locus (singular – locus, plural – loci). The presence of multiple alleles (i.e. alternative forms of a single gene) of a marker at a single locus is known as polymorphism. There are two kinds of variation (1) sequence polymorphisms and (2) length polymorphisms. Sequence polymorphisms are usually simple replacement of one or two bases in the genes themselves [5]. For example, Fig. (1) depicts the sequence polymorphism at the fifth base pair from the left.

Fig. (1). An example of sequence polymorphisms.

This is different in the case of length polymorphisms. Length polymorphisms are known as the variations in the length of the DNA molecule. For example, given three blocks of repeats (with similar DNA sequences), each block is known as a tandem repeat as shown in Fig. (2).

Fig. (2). An example of length polymorphisms.

Therefore, a locus that exhibits variation in the number of tandem repeats is known as a variable number tandem repeat (VNTR).

Research has shown that only 5% of the human genome contains useful genes. Genes are portions (sub-units) of chromosome that contain useful information and serve as templates for the production of proteins. However, the rest of the 95% of the human genome does not contain genes that code for any proteins. Sometimes this section of the human genome is known to be “junk DNA”. Until recently, studies have shown that these “junk DNA” do have important functions such as regulating gene expression, assisting in cellular machinery and serving as chromosomal structure support [3].

It is in these non-coding regions of the human genome where the VNTRs are mostly located. The number of copies of a VNTR determines the size of a DNA fragment, and each individual has a unique number of tandem repeats at specific molecular location (i.e. loci) on his or her chromosome. Essentially, this important principle serves as a building block of DNA evidence that is used today in many forensic works to allow unambiguous identification of suspects.

After gaining understanding of the scientific basis of DNA typing, we now turn to a few sequence alignment algorithms that perform appropriate tasks. In many applications of Bioinformatics, especially in the area of forensic studies, we need to examine the possible optimal alignment between two or more related sequences (i.e. be it DNA or protein sequences, these sequences can be extracted from various loci with tandem repeats or from any forensic evidences) and the close relationship between them. For this reason, it is important to include them in our studies and understand their vital roles and functions in forensic applications.

One of the simplest methods for evaluating whether two sequences are similar is to use a dot plot approach [6]-[7]. First, a matrix is constructed, with sequence A on the x-axis and sequence B on the y-axis. Begin with all the cells initialised at zero. The computation starts by taking the first character of sequence A and comparing it with all the characters of sequence B. Mark those characters of sequence A with an ‘X’ if the same character can be found in sequence B. Next, the computation advances to the next character of sequence A and the same steps are performed. Stop when all the characters in sequence A have been compared with all the characters of sequence B. At the end of the computation, a dot plot is produced as illustrated in Fig. (3).

Fig. (3). Dot Plot.

One of the shortcomings of a dot plot is that it can be complex and overcrowded with dots when the sequences become too large and similar (i.e. similar does not mean identical). Normally, identical sequences will give rise to a single diagonal line across the plot as shown in Fig. (4). Whereas in Fig. (5), similar sequences tend to produce a broken diagonal line and the gaps in between them indicates that there are mismatches between the two sequences. If the two sequences are distantly related with very few similarities, it will not only contain more diagonal lines in the direction parallel to central diagonal, but also broken diagonal lines as in Fig. (6). The distance between the central diagonal line and the surrounding sub-diagonal lines represents the correction needed by introducing gaps to align the two sequences.

Fig. (4). Comparison of two identical sequences.

Fig. (5). Comparison of two highly similar sequences.

Fig. (6). Comparison of two distantly related sequences.

Since the dot plot is particularly sensitive to noise when comparing two large sequences with similarities, one of the workaround solutions is to introduce the concept of a sliding window with a cutoff threshold. The sliding window is similar to a cart that contains a number of characters (i.e. defined by the window size), which will be used and compared with other characters in another cart. If the total number of matches between these two carts is higher than or equal to the predefined cutoff threshold, a match is found, otherwise no match is found and the sliding window then advances to the next set of characters and the process is repeated. The sliding window with a cutoff threshold helps to reduce noise in the dot plot.

An alignment between two sequences is defined as a pairwise match between the characters of each sequence. So, pairwise sequence alignment is a technique used to find the optimal pairing of sequences (i.e. can be either DNA sequences {A, C, G, T} or Protein sequence {A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y}) that preserves the order of characters in each sequence. Gaps may be introduced in the alignment process so that the total score can be maximized [6-9]. This concept can be generalised as follows in Table 1.

Table 1.

Pairwise Sequence Alignment Generalisation

Input	Two sequences Xm and Yn where m and n are the length of sequences X and Y respectively. A scoring function, s( x, y), where x ∈ Xm and y ∈ Xm      Score for character similarity (i.e. x = y)      Score for character dissimilarity (i.e. x ≠ y)      Score for gap, g (i.e. inserting a ‘-‘ character) Example:      s(x, y) = +1 if x = y, gives a score of +1 if the two character are the same      s(x, y) = -1 if x ≠ y, gives a score of -1 if the two character are not the same     g = -2, gives a score of -2 if a gap is introduced in the sequence
Task	Traverse along the two sequences and attempt to find the optimal alignment between the sequences such that the total score is maximized. During the process, gaps may be introduced to assist sequence alignment.
Output	The alignment of the two sequences with the best score. Example on DNA sequence: Example on Protein sequence:

With the generalisation and understanding of pairwise sequence alignment, we are now ready to tackle more sophisticated algorithms. The algorithms described in the following sections perform sequence alignment via dynamic programming. Dynamic programming is a concept, which refers to solving an instance of a problem by taking advantage of computed solutions for smaller subparts of the problem. Three alignment methods will be reviewed in the following sections, namely global, semi-global and liner alignment algorithms. In addition, two penalty schemes, the linear and affine gap penalties, will be discussed for each alignment method.

2.4.1. Global Alignment With Linear Gap Penalty

Regardless of the location of the gaps in a sequence, global alignment will give penalty to gaps identified during sequence comparison. As such, the entire sequence will be considered as a whole entity during the alignment process. The “Needleman and Wunsch Algorithm” is one such global sequence alignment algorithm. The algorithm is described in Table 2.

Table 2.

Global Alignment with Linear Gap Penalty Algorithm

Input:	Given sequences of S1 and S2 with length n and m respectively. Let s be the scoring scheme and g be the linear gap penalty.
Objective:	To find the best match between sequences S1 and S2 of from one end to another.
Step 1:	Compute the similarity score of the optimal global alignment with linear gap penalty. First, construct a (m+1) × (n+1) matrix M and then initialise the matrix M with the following conditions, M (0, 0) =0 M (i, 0)= i × g M (0 , j)= j × g i and j are the row and column index of matrix M respectively and g is the gap penalty from the scoring scheme. Lastly, construct the rest of the remaining cells according to the recurrence relation for global alignment with linear gap penalty:
Step 2:	In step 1, only the similarity score is computed. To find the alignment itself, we must find the path of choices that lead to this score. This is known as the traceback stage. In each cell, it saves pointer(s) to parent cell(s) that gives the optimal score (where the optimal score originated) M (i, j) contains the optimal score and the formula is as follows: M(i, j)= max {M(i-1, j-1) + s (S1[i], S2[j]),   M(i- 1, j)+ g,  M(i, j - 1)+ g}. Initialise P to an empty set, P(i, j) = ø. From the matrix top to bottom, left to right, perform the following operations to locate the traceback path for each cell. Case 1 Case 2 Case 3
Step 3:	Start from the final cell P(m, n) and follow any path back to P (0, 0). It is possible to obtain multiple alignments if there are more than one path leading to P (0, 0).
	Time complexity: O(m× n) Space complexity: O(m × n)

2.4.2. Semi-Global Alignment With Linear Gap Penalty

If the aim is to use a shorter sequence to search for a larger sequence for a possible sub-sequence match, semiglobal alignment will be a better choice as compared to the global alignment as the latter will penalise gaps at either ends of the alignment. Semi-global alignment solves this problem by not penalising gaps found at either ends of a sequence. The semi-global alignment with linear gap penalty is described in Table 3.

Table 3.

Semi-Global Alignment with Linear Gap Penalty

Input:	Given a sequence S1 of length m and a sequence S2 of length n and a scoring scheme S Linear gap penalty function: w (k) = g × k, where w(k) indicates cost of a gap of length k and g is a constant.
Objective:	To find the best match between subsequence of S1 and S2. This semi-global alignment is particularly useful when lengths of sequences differ significantly and we want to align the shorter sequence in the interior of the other or to align the suffix of one sequence to the prefix of the other.
Step 1:	Compute the similarity score of the optimal semi-global alignment with linear gap penalty. First, construct a (m+1)×(n+1) matrix M, and then initialise the matrix M with the following conditions, M (0, 0)=0 M (i, 0)=0 M (0, j)=0 i and j are the row and column index of matrix M respectively. Take note of the differences. The first row and first column of the matrix M are initialised to zeros. Lastly, construct the rest of the remaining cells according to the recurrence relation for global alignment with linear gap penalty:
Step 2:	This step is similar to the global alignment (section 2.4.1).
Step 3:	Start from the last row or the last column of matrix M with the maximum value. Trace until the cell (0, 0) is reached.
	Time complexity: O(m × n) Space complexity: O(m×n)

2.4.4. Global Alignment With Affine Gap Penalty

In many occasions, gap of length k is more probable than k gaps of length 1. This is especially so for a single mutation event that can insert or delete a stretch of characters in a sequence. In addition, distinct mutational events could also lead to separated gaps being produced. A linear gap penalty function treats all these events in the same fashion. However, the affine case distinguishes these events and treats them separately. The affine gap penalty function uses two penalties, which are the gap opening penalty, referred to as h, and the gap extension penalty referred to as g. The only difference between a global alignment with linear gap penalty and a global alignment with affine gap penalty is the penalty function being used, and instead of only one similarity matrix being computed (in linear gap penalty), three similarity matrices are being computed (in the affine gap penalty). The rest are similar. The global alignment with affine gap penalty is tabulated in Table 5.

Table 5.

Global Alignment with Affine Gap Penalty

Input:	Given sequences of S1 and S2 with length n and m respectively. Let s be the scoring scheme, h be the gap opening penalty and g be the gap extension penalty.
Step 1:	Global alignment dynamic programming algorithm for the affine gap penalty case uses three matrices instead of one.
Step 2:	This is the traceback stage. Fill in the rest of the three matrices from the top to the bottom, and from the left to the right and then store the corresponding pointers to the parent cells in each matrix.
Step 3:	Start from the cell with the largest value of either M(m, n), E(m, n) or F(m, n). Trace back pointers until the cell M(0,0) is reached.

BLAST (Basic Local Alignment Search Tool) algorithm was originally developed in 1990 by Altschul et al. and it is one of the most commonly used tools for searching sequence databases for maximal un-gapped local alignments. It is efficient and optimised for parallel computation. BLAST adopts a simple approach by taking the input sequence and breaking it down into a fixed length of words (normally length of 4). After which, these words will be used to search through the sequence databases to obtain high-scoring pairs. The BLAST search process can be summarised as follows:

Given an input sequence: ACCGTTTAAAA

Step 1: Break the query sequence into words of a fixed length (default word length of 4).

ACCGTTTAAAA → ACCG, CCGT, CGTT, GTTT, …, AAAA

Step 2: Pre-process the words by discarding those that contain common amino acids.

Step 3: Starting from “ACCG”, search the sequence databases for word matches.

Step 4: Then, extend the query sequence and repeat the search until the local alignment score falls below a certain threshold.

Step 5: Output the alignment results.

There has been much work done lately on improving sequence alignment such as Clustal W is the most commonly used multiple alignment software [12]. ClustalW can generate phylogenetic trees when a properly formatted alignment is input.

FASTA, originally developed in 1985 by Lipman et al. [11], is used to perform gapped local alignments between sequences. Similar to the BLAST technique, FASTA also breaks a query sequence into words of a fixed length, known as ktup no. For nucleotides, ktup no 4 to 6 is used, and for proteins, ktup no 1 to 2 is used. Next, a look-up table and an offset table are constructed for a query sequence and a target sequence respectively. By comparing these two tables, similar subsequences are identified. The FASTA search process can be summarised as follows:

Given a query sequence: ATGCTATAC

For a ktup no = 4, a look-up table is constructed as follows:

Given a target sequence: TGCTAT

The following offset table is constructed using ktup no = 4.

Offset by 1 (a large no. of instances of the distance 1 in the second table), we would obtain the following alignment.

The similarities and differences between the BLAST and FASTA approaches can be summarised as follows [13]. BLAST and FASTA have the following common strategies:

• Both techniques have fast screening process to eliminate unrelated sequences; and
• Both techniques are able to complete alignment of top scoring sequences.

The differences between these two techniques can be found in:

• Statistical model; and
• Heuristic and tuning.

Fig. (7) depicts the high-level system architecture of the system developed. The user interacts with the system via a GUI (Graphical User Interface) display to perform sequence alignment operations. The sequence alignment algorithms included in this work are PSA, BLAST, FASTA and Dotplot. In addition, TR is used for tandem repeats analysis. PSA, TR and Dotplot are custom-built applications using the Java SDK, whereas BLAST and FASTA are both open-source applications freely available for development use and have been integrated to the system. The rest are utilities developed to support Sequence Analysis Work. Examples are a set of database utilities for index (key) creation, data conversion, and packaging of data into the Fasta data format (i.e. BlastFastaData) for database search, which are particularly used by BLAST and FASTA algorithms. Also, BioJava utilities for creating and maintaining data (i.e. BioData) that is compatible to BioJava standard, are used by the PSA algorithm. BioJava also provides many other sequence routines, algorithms and libraries for building bio-applications. In addition, a text file editor is also developed to facilitate sequence files editing.

Fig. (7). System Architecture.

PSA, BLAST and FASTA algorithms are capable of utilising multiple CPUs for parallel execution. PSA achieves this via the Java Threading function. Java Threads are light-weight processes spawned by PSA to perform database search and sequence alignment. Open-source such as BLAST and FASTA were developed to handle multiple CPUs as well.

The GUIMain is the root user MMI Interface. It was built using the Java Frame Class. The rest of the user interfaces (such as the Dotplot MMI and PSA MMI) are to reside within this root MMI as Java Internal Frame Class. In other words, the GUIMain is the main console where everything begins.

The Dotplot software component has four input parameters as shown in Fig. (8). They are the input sequences to be compared and their homology determined via the Dotplot algorithm. The window size determines the word size on each axis to be examined, moving from left to right for the horizontal axis (sequence A) and moving from bottom to top for the vertical axis (Sequence B). A dot will be plotted on (x, y) coordinate if the number of matches between sequence A[x, x + windowsize] and sequence B[y, y + windowsize] > threshold on a diagram. The output is a plot diagram indicating those sections with two identical sequences as illustrated in Fig. (9).

Fig. (9). Dotplot Input & Output Parameters.

Fig. (8). GUIMain Java Frame vs Java Internal Frame.

A GUI was developed using the Java Internal Frame (Java Swing Library) and integrated with the Dotplot algorithm. The user specifies the input parameters, such as sequences to be compared, the window size and the threshold, and the type of file to be imported (i.e. either DNA or protein sequence file) and click on the <Apply> button to run the Dotplot program. The result of the plot is displayed on the “Results” panel as presented in Fig. (10).

Fig. (10). Dotplot GUI Layout.

The PSA software component has a number of input parameters that can be set (Fig. 11). The PSA component was implemented to perform three different types of alignment with either linear or affine gap penalty function depending on the user’s selection. They are (1) Global Alignment with linear or affine gap penalty, (2) Semi-Global Alignment with linear or affine gap penalty and (3) Local Alignment with linear or affine gap penalty.

Fig. (11). PSA Input & Output Parameters.

The PSA GUI was implemented as a Java Internal Frame. It has controls to handle all the three types of PSA discussed earlier on. That is, the user is able to select a single query sequence to search against a database containing many target sequences, or to search against a file containing multiple target sequences, or to search only one target sequence. Once the user has selected the desired option, he/she will be prompted to enter the desired values. Finally, to execute the application, the user can click on the <OK> button to run the PSA operation. The result is displayed on the “Results” text area, as seen in Fig. (12).

Fig. (12). The PSA GUI Implementation.

For the BLAST component, only the essential parameters are implemented. This is sufficient to demonstrate that the BLAST Algorithm can be integrated into the GUI and can work together as one single component for the present application. The remaining parameters can be incorporated into the existing architecture easily.

The GUI was developed from ground up. The layout was designed to accommodate a partial list of BLAST input parameters (not the full parameter list). Hitherto, the remaining input parameters are left out. However, the GUI was developed to allow future expansion in mind without too much hassle. If needed, the GUI can be extended using the Netbeans IDE GUI Editor Tool. The BLAST GUI is shown in Fig. (13).

Fig. (13). BLAST GUI Layout.

To input parameters, sequences file and target database, the user clicks on the “folder” icon. To run the BLAST application, the <OK> button is clicked. The alignment result is shown on the result text area.

FASTA, like BLAST, is also a freely available open-source application that can be downloaded from the net. Hence, it is not required to build from ground up. FASTA is incorporated together with the GUI, which is developed from scratch. Likewise, only a partial list of parameters are used, which is sufficient for concept proofing. If needed, the remaining parameters can be incorporated for future work.

The FASTA GUI is implemented and it has controls for files input and parameter settings. To execute the FASTA alignment, click on the <OK> button. The result is then displayed on the text area.

DNA fingerprinting is the foundation of most forensic applications. The uniqueness of DNA fingerprinting is based on the number of tandem repeats found in each individual “junk DNA”. It is this tandem repeats that give rise to unique identification of an individual. Therefore, TR analysis tool is included in this software implementation.

Due to the high complexity and difficulty of ATR implementation, the TR component in this implementation only handles detection of ETR as this is sufficient to demonstrate the concept of using TR Search Tool to identify potential criminals. The inclusion of ATR implementation can be considered for future work.

The inputs to TR search tool are: (1) suspect’s DNA sequence; and (2) minimum and maximum TR word size. During stage 1, the suspect’s DNA sequence is analysed and the TR tool will locate all possible ETRs found within the nucleotide sequence based on the selected TR word size. The tool allows the TR word size to be configured freely, as well as to shorten or widen the sliding window size (the sliding window is used to scan along the sequence and to locate possible TRs). Once all the possible TRs are identified, the user is able to select one or more TRs to scan the selected databases for a possible match. If one or more matches are found, the results are displayed on the MMI. See Fig. (14).

Fig. (14). TR search tool parameters.

Fig. (15) depicts the GUI layout of the tandem repeats search tool. To upload a suspect’s DNA sequence, click on the “folder” button. A file selector dialog will be prompted. Enter a minimum and maximum word size for the TR search. Click on the “Enter” button to start analysing the DNA sequence. The TR algorithm will perform TR analysis on the sequence being entered. All the possible ETRs are displayed in the STR Word Text Area. For instance, “ATG (3)” means that “ATG” is found to be a continuous TR within the sequence and “(3)” means that there are three such TRs.

Fig. (15). Tandem Repeats Search Tool.

The next step is to select one or more STR words to scan through one or more databases (multiple selection of databases are allowed). Click <OK> to execute the database scan and the final results of the suspect’s ID and the associated DNA sequence in the databases.

As Bioinformatics advances, there is an ever-increasing need to store large amounts of biological data for analysis work. It is common to work with very large sequence databases that are unable to fit into the current physical memory available. Hence, the preferred way to handle large amounts of biological sequence is to use a dedicated database system. FASTA and BLAST provides a “Fasta” format database for this purpose. They use the “formatdb” routine to create their databases. BioJava also provides a set of library APIs (Application Programming Interfaces) for data creation, update and modification.

As such, a number of database tools have been developed in this work for such purposes and are summarised as follows:

1. Tool to create “Fasta” format database:
   1. The “Fasta” format is widely accepted by FASTA and BLAST applications. In fact, it is one of the most widely used data format in many of the third-party applications.
   2. In this work, both of the FASTA and BLAST use this format.
2. Tool to create BioJava compatible format database:
   1. BioJava offers a simple and efficient sequence database implementation backed by one or more sequence files on disk. These files can be in any format, as long as a suitable sequence format class exists.
   2. The current PSA software component uses this format.
3. Text File Editor:
   1. To create, modify and update sequence or database files.

To create a local customised database for BLAST and FASTA applications, the “formatdb” routine, which is provided by the BLAST and FASTA packages, is used. However, it is rather inconvenient to use the “formatdb” command manually via the command line input. Therefore, a GUI is developed to provide a more user-friendly interaction.

To upload a file containing the sequences, click on the “folder” icon. After that, select the appropriate file type. Choose either “NUCLEOTIDE” for DNA sequences or “PROTEIN” for protein sequences. By default, it is set to “FALSE” for parse output. Click the <OK> button when done to initiate database creation.

For the PSA component, the BioJava compatible format database is used. However, BioJava Library only provides a list of APIs, and hence there is a need to build these database tools.

The first database tool is the “Create DB Index” routine. This routine is responsible for creating a BioJava DB Index for storing all the sequences on disk. It functions like a schema. Fig. (16) depicts the GUI layout.

Fig. (16). Database tool for creating BioJava compatible database.

The second database tool is the “Add File To DB”. This routine is responsible for uploading all the sequences to the DB Index created earlier on. Only when this step has been executed, then can the DB be populated with data.

The last database tool is for listing all the sequence IDs associated with a particular database. It is useful when a global listing of sequence IDs is required.

The sequence file-editing tool is responsible for creating; updating and modifying sequence files or sequence databases. These files can then be uploaded via the appropriate database tools into various data formats, which can be used, by BLAST, FASTA and PSA.

The data used for testing the software tools is generated from a custom-built software program. Fig. (17) shows the program has four parameters, which are:

Fig. (17). GenerateTestData() Input & Output Parameters.

1. Record Size - the number of records to be created;
2. Repeat Word - the TR pattern to be inserted into the test data;
3. Random Seed - to add in random variation; and
4. Record Name - the record name for each sequence generated. It is postfix by a unique ID generated by the computer.

The output data of this program is in the “FASTA” format.