Partitional clustering algorithms for highly similar and sparseness y-short tandem repeat data / Ali Seman

Seman, Ali (2013) Partitional clustering algorithms for highly similar and sparseness y-short tandem repeat data / Ali Seman. PhD thesis, Universiti Teknologi MARA.


Clustering is an overlapping method found in many areas such as data mining, machine learning, pattern recognition, bioinformatics and information retrieval. The goal of clustering is to group any similar objects into a cluster, while the other objects that are not similar in the different clusters. Meanwhile, Y-Short Tandem Repeats (YSTR) is the tandem repeats on Y-Chromosome. The Y-STR data is now being utilized for distinguishing lineages and their relationships applied in many applications such as genetic genealogy, forensic genetic and anthropological genetic applications. This research tends to partition the Y-STR data into groups of similar genetic distances. The genetic distance is measured by comparing the allele values and their modal haplotypes. Nevertheless, the distances among the Y-STR data are typically found similar or very similar to each other. They are characterized by the higher degree of similarity of objects in intra-classes and also inter-classes. In some cases, they are quite distant and sparseness. This uniqueness of Y-STR data has become problematic in partitioning the data using the existing partitional clustering algorithms. The main problem was essentially caused by the mode mechanism (problem P?) which was unable to handle the characteristics of Y-STR data, thus producing poor clustering results. The problem has become worst when the initial centroid selection which is also known as problem Po failed to obtain good centroids. These conditions have led the existing partitional algorithms to local minima and empty clusters problems. As a result, a new idea of problem P2 using the objects (medoid) themselves was introduced. The idea was incorporated into a new algorithm called, k-Approximate Modal Haplotypes (&-AMH) algorithm. Six Y-STR data sets were used as a benchmark to evaluate the performances of the algorithm against the other eight partitional clustering algorithms. Out of six data sets, the &-AMH algorithm obtained the highest mean accuracy scores for the five data sets and one data set was at equal performance. For the overall performances which were based on the six data sets, the &-AMH algorithm recorded the highest mean accuracy scores of 0.93 as compared to the other algorithms: the ^-Population (0.91), the &-Modes-RVF (0.81), the New Fuzzy &-Modes (0.80), A:-Modes (0.76), &-Modes-HI (0.76), £-Modes- HII (0.75), Fuzzy £-Modes (0.74) and £-Modes-UAVM (0.70). A One-Way ANOVA
test also indicated that the clustering accuracy scores of &-AMH algorithm was significantly different as compared to the other eight partitional algorithms. In addition, the algorithm was also efficient in terms of time complexity which was recorded as O (km(n-k) and considered as linear. Thus, the &-AMH algorithm has been bounded with good characteristics of a desired algorithm - scalability.


Item Type: Thesis (PhD)
Email / ID Num.
Seman, Ali
Subjects: Q Science > QA Mathematics > Evolutionary programming (Computer science). Genetic algorithms > Malaysia
Divisions: Universiti Teknologi MARA, Shah Alam > Faculty of Computer and Mathematical Sciences
Keywords: Clustering; Algorith
Date: 2013
Edit Item
Edit Item


[thumbnail of TP_ALI SEMAN CS 13_5.pdf] Text
TP_ALI SEMAN CS 13_5.pdf

Download (1MB)

Digital Copy

Digital (fulltext) is available at:

Physical Copy

Physical status and holdings:
Item Status:

ID Number




Statistic details