- MSc thesis
- Βιοπληροφορική και Νευροπληροφορική (ΒΝΠ)
- 19 Φεβρουαρίου 2023
- Ελληνικά
- 104
- ΑΜΑΝΑΤΙΔΗΣ, ΔΗΜΗΤΡΙΟΣ
- ΛΑΓΚΟΥΒΑΡΔΟΣ, ΗΛΙΑΣ΄ | ΧΑΤΖΗΝΙΚΟΛΑΟΥ, ΜΑΡΙΑ, ΚΑΘΗΓΗΤΡΙΑ ΤΟΥ ΕΛΛΗΝΙΚΟΥ ΑΝΟΙΧΤΟΥ ΠΑΝΕΠΙΣΤΗΜΙΟΥ
- πολλαπλή στοίχιση ακολουθιών, στοίχιση κατά ζεύγη, αλγόριθμοι, φυλογενετική ανάλυση, πρόγνωση δευτεροταγούς δομής, εργαλεία αξιολόγησης πολλαπλής στοίχισης
- ΒΝΠ55
- 6
- 159
-
-
Οι προσπάθειες για τη δημιουργία βάσεων δεδομένων βιολογικών αλληλουχιών οδήγησε στη συλλογή και αποθήκευση ιδιαίτερα μεγάλου όγκου δεδομένων τα οποία χρήζουν περαιτέρω ανάλυσης. Σημαντική πρόκληση στην επεξεργασία τους, αποτελεί η σύγκριση των αλληλουχιών, που επιτυγχάνεται με τη στοίχισή τους, η οποία μπορεί να γίνεται είτε κατά ζεύγη (Pairwise Sequence Alignment, PSA), είτε ως πολλαπλή στοίχιση (Multiple Sequence Alignment, MSA), όταν ο αριθμός των αλληλουχιών είναι μεγαλύτερος από δυο. Οι μέθοδοι που χρησιμοποιούνται στη στοίχιση κατά ζεύγη είναι το διάγραμμα σημείων (dot-matrix), οι πίνακες ομοιότητας, ο δυναμικός προγραμματισμός, η word ή k-tuple μέθοδος (λέξεων ή λέξεων με μέγεθος k), η sum of pairs (SP) σκορ, FASTA και BLAST. Η πολλαπλή στοίχιση βρίσκει μεγάλη εφαρμογή στη φυλογενετική ανάλυση, καθώς και στην πρόγνωση της δευτεροταγούς δομής των πρωτεϊνών. Οι αλγόριθμοι πολλαπλής στοίχισης μπορεί να είναι βέλτιστοι, να υπολογίζουν δηλαδή τη βέλτιστη στοίχιση με βάση κάποια συνάρτηση σκορ, ή ευριστικοί, υπολογίζοντας τη στοίχιση χρησιμοποιώντας κάποια βιολογικά βάσιμη διαδικασία (πχ προοδευτική στοίχιση). Υπάρχουν πολλά αξιόπιστα προγράμματα για πολλαπλή στοίχιση και χρειάζεται προσοχή κατά την επιλογή του καταλληλότερου για την εκάστοτε ανάλυση. Τα κυριότερα είναι η οικογένεια Clustal, τα DIAlign, DLPAlign, Kalign, MAFFT, MUSCLE, T-Coffee, PASTA, PRANK, PIMA, και ProbCons. Πριν από την εκτέλεση της πολλαπλής στοίχισης, αλληλουχίες που εμφανίζουν ομοιότητα ομαδοποιούνται με χρήση αντίστοιχων αλγορίθμων, όπως η διαμερισματική ομαδοποίηση μέσω του K-means, η fuzzy C-means, η πιθανοτική ομαδοποίηση, και η ιεραρχική ομαδοποίηση. Η δημιουργία κάθε φυλογενετικού δέντρου βασίζεται σε έναν πίνακα γενετικών διαφορών και για την κατασκευή του δέντρου, χρησιμοποιούνται μεταξύ άλλων είτε μέθοδοι βασισμένες στην απόσταση, είτε μέθοδοι βασισμένες στους χαρακτήρες. Στις πιο δημοφιλείς μεθόδους βασισμένες στην απόσταση συγκαταλέγονται η μέθοδος ένωσης γειτόνων (neighborhood-joining, NJ), η μέθοδος UPGMA (Unweighted Pair Group using Arithmetic Mean), η σταθμισμένη έκδοση της UPGMA, WPGMA (Weighted Pair Group using Arithmetic Mean), και η μέθοδος των Fitch-Margoliash. Ευρέως διαδεδομένες μέθοδοι βασισμένες στους χαρακτήρες αποτελούν η μέθοδος της μέγιστης φειδωλότητας (Maximum Parsimony ή MP) και η μέθοδος της μέγιστης πιθανοφάνειας (Maximum Likelihood). Η αξιοπιστία των αποτελεσμάτων της πολλαπλής στοίχισης γίνεται με εργαλεία όπως τα BAliBASE, BRAliBASE, PREFAB, OXBENCH, SABmark, και IRMBASE, ενώ ο έλεγχος σημαντικότητας επιτυγχάνεται με μεθόδους επανα-δειγματοληψίας όπως η bootstrap. Τέλος, η εφαρμογή προσεγγίσεων όπως η μηχανική μάθηση, οι κάρτες γραφικών, η τεχνητή νοημοσύνη και τα νευρωνικά δίκτυα ανοίγουν τον δρόμο για ακόμα σπουδαιότερες μελλοντικές εξελίξεις στον τομέα της πολλαπλής στοίχισης.
-
Efforts to create databases of biological sequences have led to the collection and storage of large amounts of data that require further analysis. A major challenge that arises in the analysis process is the comparison of sequences, which is achieved by their alignment. This is executed either in pairs (pairwise sequence alignment, PSA), or by conducting multiple alignment (multiple sequence alignment, MSA), when the number of sequences is greater than two. The methods mainly used in pairwise alignment are dot-matrix, similarity matrices, dynamic programming, the word or k-tuple method (of words or words of size k), the sum of pairs (SP) score method, the FASTA method and BLAST. Multiple alignment is widely used in phylogenetic analysis as it groups together homologous residues that bear maximum similarity and in the prediction of the secondary protein structure. Multiple alignment algorithms can be optimal, i.e. calculate the best alignment based on some score function (eg SPscore), or heuristics, i.e. calculate the alignment based on some biologically valid process (eg progressive alignment). Nowadays, many reliable programs for multiple alignment are available, in order to choose the most appropriate for each type of analysis. The main programs used in multiple alignment are the Clustal family, DIAlign, Kalign, MAFFT, MUSCLE, T-Coffee, PASTA, PRANK, PIMA, and ProbCons. Before performing the multiple alignment, sequences that show similarity are grouped into groups (clusters), through a variety of algorithms for clustering, such as partitioned clustering through the K-means algorithm, fuzzy C-means, probabilistic clustering, and hierarchical grouping. The construction of each phylogenetic tree is based on a matrix of genetic differences obtained from the raw data. To build the tree, either distance-based or character-based methods are mainly used, are mainly used, while there are also some other less popular methods. The most popular distance-based methods include neighborhood-joining (NJ), UPGMA (Unweighted Pair Group using Arithmetic Mean), the weighted version of UPGMA, WPGMA (Weighted Pair Group using Arithmetic Mean), and Fitch-Margoliash method. Widely used character-based methods are Maximum Parsimony (MP) and Maximum Likelihood. Reliability of multiple alignment results is performed with the use of tools such as BAliBASE, BRAliBASE, PREFAB, OXBENCH, SABmark, and IRMBASE. Significance testing is achieved with re-sampling methods such as bootstrap. Finally, the use of tools such as graphics cards or approaches such as machine learning, artificial intelligence and neural networks pave the way for even greater future developments in the field of multiple alignment.
-
- Hellenic Open University
- Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές