Tree alignment
ಕಂಪ್ಯೂಟೇಶನಲ್ ಫೈಲೋಜೆನೆಟಿಕ್ಸ್ನಲ್ಲಿ, ಮರದ ಜೋಡಣೆಯು ಅನೇಕ ಅನುಕ್ರಮ ಜೋಡಣೆಗಳನ್ನು ಉತ್ಪಾದಿಸುವ ಅಥವಾ ಡಿಎನ್ಎ, ಆರ್ಎನ್ಎ ಅಥವಾ ಪ್ರೋಟೀನ್ನ ಮೂರು ಅಥವಾ ಹೆಚ್ಚಿನ ಅನುಕ್ರಮಗಳ ಜೋಡಣೆಗೆ ಸಂಬಂಧಿಸಿದ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಅನುಕ್ರಮಗಳನ್ನು ಜಾತಿಗಳ ಅಥವಾ ವರ್ಗಗಳ ನಡುವಿನ ವಿಕಸನೀಯ ಸಂಬಂಧಗಳನ್ನು ರೂಪಿಸುವ ಫೈಲೋಜೆನೆಟಿಕ್ ಮರವಾಗಿ ಜೋಡಿಸಲಾಗಿದೆ. ಪ್ರತಿಯೊಂದು ಮರದ ಆಂತರಿಕ ಶೃಂಗಗಳಿಗೆ ಅನುಕ್ರಮಗಳ ನಡುವಿನ ಸಂಪಾದನೆಯ ಅಂತರವನ್ನು ಲೆಕ್ಕ ಹಾಕಲಾಗುತ್ತದೆ, ಅಂದರೆ ಮರದೊಳಗಿನ ಎಲ್ಲಾ ಸಂಪಾದನೆಯ ಅಂತರಗಳ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡಲಾಗುತ್ತದೆ. ಮರದ ಜೋಡಣೆಯನ್ನು ನಿರ್ವಹಿಸಬಹುದಾದ ಮರದ ಗಾತ್ರ ಮತ್ತು ಕಂಪ್ಯೂಟೇಶನಲ್ ಪ್ರಯತ್ನದ ನಡುವಿನ ವಿವಿಧ ವಿನಿಮಯಗಳೊಂದಿಗೆ ಹಲವಾರು ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಒಂದನ್ನು ಬಳಸಿಕೊಂಡು ಸಾಧಿಸಬಹುದು. ವ್ಯಾಖ್ಯಾನ ಇನ್ಪುಟ್ಃ ಅನುಕ್ರಮಗಳ ಒಂದು ಸೆಟ್, ಫೈಲೋಜೆನೆಟಿಕ್ ಟ್ರೀ ಲೀಫ್-ಲೇಬಲ್ ಮತ್ತು ಅನುಕ್ರಮಗಳ ನಡುವೆ ಎಡಿಟ್ ಡಿಸ್ಟೆನ್ಸ್ ಫಂಕ್ಷನ್. ಔಟ್ಪುಟ್ಃ ಕನಿಷ್ಠಗೊಳಿಸಲಾದ ಆಂತರಿಕ ಶೃಂಗಗಳ ಲೇಬಲಿಂಗ್, ಅದರ ಅಂತಿಮ ಬಿಂದುಗಳ ನಡುವಿನ ಸಂಪಾದನೆಯ ಅಂತರ ಎಲ್ಲಿದೆ. ಈ ಕಾರ್ಯವು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ. ಹಿನ್ನೆಲೆ ಅನುಕ್ರಮ ಜೋಡಣೆ ಬಯೋಇನ್ಫರ್ಮ್ಯಾಟಿಕ್ಸ್ನಲ್ಲಿ, ಮಾಹಿತಿ ಸಂಸ್ಕರಣೆಯ ಮೂಲ ವಿಧಾನವೆಂದರೆ ಅನುಕ್ರಮ ದತ್ತಾಂಶವನ್ನು ವ್ಯತಿರಿಕ್ತಗೊಳಿಸುವುದು. ಜೈವಿಕ ಅನುಕ್ರಮಗಳಲ್ಲಿ ಕಾರ್ಯ, ರಚನೆ ಮತ್ತು ವಿಕಸನೀಯ ಮಾಹಿತಿಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜೀವಶಾಸ್ತ್ರಜ್ಞರು ಇದನ್ನು ಬಳಸುತ್ತಾರೆ. ಈ ಕೆಳಗಿನ ವಿಶ್ಲೇಷಣೆಗಳು ಅನುಕ್ರಮ ಜೋಡಣೆಯನ್ನು ಆಧರಿಸಿವೆಃ ಫೈಲೋಜೆನೆಟಿಕ್ ವಿಶ್ಲೇಷಣೆ, ಹ್ಯಾಪ್ಲೋಟೈಪ್ ಹೋಲಿಕೆ ಮತ್ತು ಆರ್ಎನ್ಎ ರಚನೆಯ ಮುನ್ಸೂಚನೆ. ಆದ್ದರಿಂದ, ಅನುಕ್ರಮ ಜೋಡಣೆಯ ದಕ್ಷತೆಯು ಈ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವ ಪರಿಣಾಮಕಾರಿತ್ವದ ಮೇಲೆ ನೇರವಾಗಿ ಪರಿಣಾಮ ಬೀರುತ್ತದೆ. ತರ್ಕಬದ್ಧ ಮತ್ತು ಪರಿಣಾಮಕಾರಿ ಅನುಕ್ರಮ ಜೋಡಣೆಯನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸುವ ಸಲುವಾಗಿ, ಅಲ್ಗಾರಿದಮ್ ವ್ಯುತ್ಪತ್ತಿಯು ಬಯೋಇನ್ಫರ್ಮ್ಯಾಟಿಕ್ಸ್ ಕ್ಷೇತ್ರದಲ್ಲಿ ಸಂಶೋಧನೆಯ ಪ್ರಮುಖ ಶಾಖೆಯಾಗುತ್ತದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಅನುಕ್ರಮ ಜೋಡಣೆ ಎಂದರೆ ಅಕ್ಷರಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ, ಅಕ್ಷರಗಳನ್ನು ಅಳಿಸುವ ಮೂಲಕ ಅಥವಾ ಪ್ರತಿ ಸ್ಟ್ರಿಂಗ್ಗೆ ಜಾಗವನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ತಂತಿಗಳಿಂದ ಹೆಚ್ಚಿನ ಹೋಲಿಕೆಯನ್ನು ಹೊಂದಿರುವ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ನಿರ್ಮಿಸುವುದು ಎಂದರ್ಥ. ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆ ಸಮಸ್ಯೆಯು ಸಾಮಾನ್ಯವಾಗಿ ಜೋಡಿಯಾಗಿ ಅನುಕ್ರಮ ಜೋಡಣೆಯನ್ನು ಆಧರಿಸಿದೆ ಮತ್ತು ಪ್ರಸ್ತುತ, ಜೋಡಿಯಾಗಿ ಅನುಕ್ರಮ ಜೋಡಣೆ ಸಮಸ್ಯೆಗೆ, ಜೀವಶಾಸ್ತ್ರಜ್ಞರು ಅದರ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವನ್ನು ಪಡೆಯಲು ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ವಿಧಾನವನ್ನು ಬಳಸಬಹುದು. ಆದಾಗ್ಯೂ, ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆಯ ಸಮಸ್ಯೆಯು ಇನ್ನೂ ಬಯೋಇನ್ಫರ್ಮ್ಯಾಟಿಕ್ಸ್ನಲ್ಲಿ ಹೆಚ್ಚು ಸವಾಲಿನ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. ಏಕೆಂದರೆ ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆಗೆ ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆ ಎಂದು ಸಾಬೀತಾಗಿದೆ ಮತ್ತು ಅಂದಾಜು ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಮಾತ್ರ ಪಡೆಯಬಹುದು. ಡಿಸ್ಟೆನ್ಸ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ವಿಧಾನವು ಅಕ್ಷರಗಳ ಒಳಸೇರಿಸುವಿಕೆ, ಅಳಿಸುವಿಕೆ ಮತ್ತು ಬದಲಿಗಳ ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆಯ ಸಂಖ್ಯೆಯನ್ನು ಅಳೆಯುತ್ತದೆ, ಇದು ಒಂದು ಜೋಡಿ ತಂತಿಗಳ ಮೇಲೆ ಕಾರ್ಯನಿರ್ವಹಿಸುವಾಗ ಒಂದು ಅನುಕ್ರಮವನ್ನು u ಅನ್ನು ಇನ್ನೊಂದು ಅನುಕ್ರಮ v ಗೆ ಪರಿವರ್ತಿಸಲು ಅಗತ್ಯವಾಗಿರುತ್ತದೆ. ಸಂಪಾದನೆಯ ಅಂತರದ ಲೆಕ್ಕಾಚಾರವು ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅನ್ನು ಆಧರಿಸಿರಬಹುದು, ಮತ್ತು ಸಮೀಕರಣವು O (|u | × |v |) ಸಮಯದಲ್ಲಿದೆ, ಅಲ್ಲಿ |u | ಮತ್ತು |v | ಗಳು u ಮತ್ತು v ನ ಉದ್ದಗಳಾಗಿವೆ. ಎಡಿಟ್ ದೂರವನ್ನು ಲೆಕ್ಕ ಹಾಕಲು ಬಳಸಲಾಗುವ ಕಾರ್ಯಗಳ ಸರಣಿಯಿಂದಾಗಿ, ವಿಭಿನ್ನ ಕಾರ್ಯಗಳು ವಿಭಿನ್ನ ಫಲಿತಾಂಶಗಳಿಗೆ ಕಾರಣವಾಗಬಹುದು. ಮರದ ಜೋಡಣೆಯ ಸಮಸ್ಯೆಗೆ ಸೂಕ್ತವಾದ ಎಡಿಟ್ ಡಿಸ್ಟೆನ್ಸ್ ಫಂಕ್ಷನ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಅತ್ಯಗತ್ಯ. ಮರದ ಜೋಡಣೆಯ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಗೆ ಕಾರಣವಾಗುತ್ತದೆ, ಅಲ್ಲಿ ಸ್ಕೋರಿಂಗ್ ವಿಧಾನಗಳು ಮತ್ತು ವರ್ಣಮಾಲೆಯ ಗಾತ್ರಗಳನ್ನು ನಿರ್ಬಂಧಿಸಲಾಗಿದೆ. ಇದನ್ನು ಅಲ್ಗಾರಿದಮ್ ಆಗಿ ಕಾಣಬಹುದು, ಇದನ್ನು ಆಪ್ಟಿಮೈಸ್ಡ್ ಪರಿಹಾರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬಳಸಲಾಗುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಅದರ ದಕ್ಷತೆ ಮತ್ತು ಸಂಖ್ಯೆಯ ಅನುಕ್ರಮಗಳ ನಡುವೆ ಘಾತೀಯ ಸಂಬಂಧವಿದೆ, ಅಂದರೆ ಅನುಕ್ರಮದ ಉದ್ದವು ತುಂಬಾ ದೊಡ್ಡದಾಗಿದ್ದಾಗ, ಫಲಿತಾಂಶಗಳನ್ನು ಪಡೆಯಲು ಅಗತ್ಯವಾದ ಗಣನೆಯ ಸಮಯವು ಅಗಾಧವಾಗಿ ದೀರ್ಘವಾಗಿರುತ್ತದೆ. ಅಂದಾಜು ಆಪ್ಟಿಮೈಸ್ಡ್ ಪರಿಹಾರವನ್ನು ಪಡೆಯಲು ಸ್ಟಾರ್ ಜೋಡಣೆಯನ್ನು ಬಳಸುವುದು ಮರದ ಜೋಡಣೆಯನ್ನು ಬಳಸುವುದಕ್ಕಿಂತ ವೇಗವಾಗಿರುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಬಹು-ಅನುಕ್ರಮ ಹೋಲಿಕೆಯ ಮಟ್ಟ ಏನೇ ಇರಲಿ, ನಕ್ಷತ್ರ ಜೋಡಣೆಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಅನುಕ್ರಮ ಸಂಖ್ಯೆಯ ವರ್ಗ ಮತ್ತು ಅನುಕ್ರಮ ಸರಾಸರಿ ಉದ್ದದ ವರ್ಗದೊಂದಿಗೆ ಅನುಪಾತದ ಸಂಬಂಧವನ್ನು ಹೊಂದಿದೆ. ಎಂದಿನಂತೆ, ಎಂಎಸ್ಎಯಲ್ಲಿನ ಅನುಕ್ರಮವು ಎಷ್ಟು ಉದ್ದವಾಗಿದೆ ಎಂದರೆ ಅದು ಅಸಮರ್ಥವಾಗಿದೆ ಅಥವಾ ಸ್ವೀಕಾರಾರ್ಹವಲ್ಲ. ಆದ್ದರಿಂದ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ರೇಖೀಯವಾಗಿ ಕಡಿಮೆ ಮಾಡುವ ಸವಾಲು ಮರದ ಜೋಡಣೆಯ ಪ್ರಮುಖ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಕಾರ್ಯತಂತ್ರವು ಎಂ. ಎಸ್. ಎ. ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಉತ್ತಮ ಕಾರ್ಯತಂತ್ರವಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆಯನ್ನು ಜೋಡಿ ಅನುಕ್ರಮ ಜೋಡಣೆಯಾಗಿ ಪರಿವರ್ತಿಸುವುದು ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಕಾರ್ಯತಂತ್ರದ ಕಲ್ಪನೆಯಾಗಿದೆ. ಅದರ ಪರಿವರ್ತನೆಯ ಕಾರ್ಯತಂತ್ರವನ್ನು ಅವಲಂಬಿಸಿ, ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಕಾರ್ಯತಂತ್ರವನ್ನು ಟ್ರೀ ಅಲೈನ್ಮೆಂಟ್ ಅಲ್ಗಾರಿದಮ್ ಮತ್ತು ಸ್ಟಾರ್ ಅಲೈನ್ಮೆಂಟ್ ಅಲ್ಗಾರಿದಮ್ ಎಂದು ವಿಂಗಡಿಸಬಹುದು. ಕೊಟ್ಟಿರುವ ಬಹು-ಅನುಕ್ರಮ ಸೆಟ್ = {,.,} ಗೆ, n ಎಲೆಯ ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುವ ವಿಕಸನೀಯ ಮರವನ್ನು ಹುಡುಕಿ ಮತ್ತು ಈ ವಿಕಸನೀಯ ಮರ ಮತ್ತು ಗುಂಪಿನ ನಡುವೆ ಒಂದರಿಂದ ಒಂದು ಸಂಬಂಧವನ್ನು ಸ್ಥಾಪಿಸಿ. ವಿಕಸನೀಯ ಮರದ ಆಂತರಿಕ ಗ್ರಂಥಿಗಳಿಗೆ ಅನುಕ್ರಮವನ್ನು ನಿಯೋಜಿಸುವ ಮೂಲಕ, ನಾವು ಪ್ರತಿ ಅಂಚಿನ ಒಟ್ಟು ಅಂಕವನ್ನು ಲೆಕ್ಕ ಹಾಕುತ್ತೇವೆ ಮತ್ತು ಎಲ್ಲಾ ಅಂಚುಗಳ ಅಂಕಗಳ ಮೊತ್ತವು ವಿಕಸನೀಯ ಮರದ ಅಂಕವಾಗಿದೆ. ಮರದ ಜೋಡಣೆಯ ಗುರಿಯು ನಿಗದಿಪಡಿಸಿದ ಅನುಕ್ರಮವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ಅದು ಗರಿಷ್ಠ ಅಂಕವನ್ನು ಪಡೆಯಬಹುದು ಮತ್ತು ವಿಕಾಸಾತ್ಮಕ ಮರ ಮತ್ತು ಅದರ ನೋಡ್ಗಳ ನಿಗದಿಪಡಿಸಿದ ಅನುಕ್ರಮದಿಂದ ಅಂತಿಮ ಹೊಂದಾಣಿಕೆಯ ಫಲಿತಾಂಶವನ್ನು ಪಡೆಯಬಹುದು. ನಕ್ಷತ್ರದ ಜೋಡಣೆಯನ್ನು ಮರದ ಜೋಡಣೆಯ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ಕಾಣಬಹುದು. ನಾವು ನಕ್ಷತ್ರ ಜೋಡಣೆಯನ್ನು ಬಳಸುವಾಗ, ವಿಕಸನೀಯ ಮರವು ಕೇವಲ ಒಂದು ಆಂತರಿಕ ನೋಡ್ ಮತ್ತು ಎನ್ ಲೀಫ್ ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆಂತರಿಕ ನೋಡ್ಗೆ ನಿಗದಿಪಡಿಸಲಾದ ಅನುಕ್ರಮವನ್ನು ಕೋರ್ ಸೀಕ್ವೆನ್ಸ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಕೀವರ್ಡ್ ಟ್ರೀ ಸಿದ್ಧಾಂತ ಮತ್ತು ಅಹೋ-ಕೋರಾಸಿಕ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆಯನ್ನು ಜೋಡಿ ಅನುಕ್ರಮ ಜೋಡಣೆಯಾಗಿ ಪರಿವರ್ತಿಸಲು ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ತಂತ್ರವನ್ನು ಬಳಸಿದಾಗ, ಮುಖ್ಯ ಸಮಸ್ಯೆಯನ್ನು "ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆಯ ದಕ್ಷತೆಯನ್ನು ಹೇಗೆ ಸುಧಾರಿಸುವುದು" ನಿಂದ "ಜೋಡಿಯಾಗಿ ಅನುಕ್ರಮ ಜೋಡಣೆಯ ದಕ್ಷತೆಯನ್ನು ಹೇಗೆ ಸುಧಾರಿಸುವುದು" ಎಂದು ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ. ಕೀವರ್ಡ್ ಟ್ರೀ ಥಿಯರಿ ಮತ್ತು ಅಹೋ-ಕೋರಾಸಿಕ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಜೋಡಿಯಾಗಿ ಅನುಕ್ರಮ ಜೋಡಣೆಯ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಒಂದು ಪರಿಣಾಮಕಾರಿ ವಿಧಾನವಾಗಿದೆ. ಕೀವರ್ಡ್ ಟ್ರೀ ಸಿದ್ಧಾಂತ ಮತ್ತು ಅಹೋ-ಕೋರಾಸಿಕ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಂಯೋಜಿಸುವ ಗುರಿಯು ಈ ರೀತಿಯ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದುಃ ನಿರ್ದಿಷ್ಟ ಉದ್ದದ ಸ್ಟ್ರಿಂಗ್ ಮತ್ತು ಸಣ್ಣ ಸ್ಟ್ರಿಂಗ್ಗಳ ಗುಂಪಿಗೆ = {,,.,} (z bul N, z> 1), ಎಲ್ಲದರ ಸ್ಥಳವನ್ನು ಹುಡುಕಿ. ಸೆಟ್ನಿಂದ ಉತ್ಪತ್ತಿಯಾಗುವ ಕೀವರ್ಡ್ ಟ್ರೀ ಅನ್ನು ಬಳಸಲಾಗುತ್ತದೆ, ಮತ್ತು ನಂತರ ಅಹೋ-ಕೋರಾಸಿಕ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಮೂಲಕ ಈ ಕೀವರ್ಡ್ ಟ್ರೀ ಮೂಲಕ ಹುಡುಕಲಾಗುತ್ತದೆ. ಟಿ ಯಲ್ಲಿ ಎಲ್ಲದರ ಸ್ಥಳವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಈ ವಿಧಾನವನ್ನು ಬಳಸುವ ಒಟ್ಟು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಒ (+ +) ಆಗಿದೆ, ಅಲ್ಲಿ = | | (ಉದ್ದ), = ಎ | | (ಎಲ್ಲದರ ಉದ್ದಗಳ ಮೊತ್ತ) ಮತ್ತು ಎಲ್ಲದರ ಸಂಭವದ ಮೊತ್ತವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಕೀವರ್ಡ್ ಟ್ರೀ ಸಿದ್ಧಾಂತ ಗುಂಪಿನ ಕೀವರ್ಡ್ ಟ್ರೀ = {,,.,} (z bul N, z> 1) ಒಂದು ಬೇರೂರಿರುವ ಮರವಾಗಿದೆ, ಇದರ ಮೂಲವನ್ನು K ಸೂಚಿಸುತ್ತದೆ, ಮತ್ತು ಈ ಕೀವರ್ಡ್ ಟ್ರೀ ತೃಪ್ತಿಪಡಿಸುತ್ತದೆಃ (1): ಪ್ರತಿ ಅಂಚು ಸ್ಪಷ್ಟವಾಗಿ ಒಂದು ಅಕ್ಷರವನ್ನು ಗುರುತಿಸುತ್ತದೆ. (2): ಒಂದೇ ನೋಡ್ನಿಂದ ಬೇರ್ಪಟ್ಟ ಯಾವುದೇ ಎರಡು ಅಂಚುಗಳು ವಿಭಿನ್ನ ಅಕ್ಷರಗಳಿಗೆ ಹೊಂದಿಕೆಯಾಗುತ್ತವೆ. (3) ಪ್ರತಿಯೊಂದು ಮಾದರಿಯು (i = 1,2,., z) ಒಂದು ನೋಡ್ಗೆ ಅನುರೂಪವಾಗಿದೆ, ಮತ್ತು ಮೂಲ K ಯಿಂದ ನೋಡ್ಗೆ ಹೋಗುವ ಮಾರ್ಗವು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ನಿಖರವಾಗಿ ಸರಿಯಾಗಿ ಉಚ್ಚರಿಸಬಹುದು. ಈ ಕೆ ಮರದ ಪ್ರತಿ ಎಲೆಯ ನೋಡ್ಗೆ, ಇದು ಗುಂಪಿನ ನಿರ್ದಿಷ್ಟ ಮಾದರಿಗಳಲ್ಲಿ ಒಂದಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ. ರೂಟ್ ನೋಡ್ನಿಂದ ನೋಡ್ಗೆ ಸಂಪರ್ಕಗೊಂಡಿರುವ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಇದನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ನಂತರ ಉದ್ದವಾದ ಪ್ರತ್ಯಯದ ಉದ್ದವನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ (ಅಲ್ಲದೆ, ಈ ಪ್ರತ್ಯಯವು ಗುಂಪಿನಲ್ಲಿನ ಮಾದರಿಗಳಲ್ಲಿ ಒಂದರ ಪೂರ್ವಪ್ರತ್ಯಯವಾಗಿದೆ). ಕೀವರ್ಡ್ ಟ್ರೀಯಲ್ಲಿರುವ ಮೂಲ ನೋಡ್ನಿಂದ ಈ ಪೂರ್ವಪ್ರತ್ಯಯವನ್ನು ಹುಡುಕುವುದು, ಮತ್ತು ಹುಡುಕಾಟವು ಮುಗಿದ ನಂತರ ಸೂಚಿಸಲಾದ ಕೊನೆಯ ನೋಡ್. ಉದಾಹರಣೆಗೆ, ಸೆಟ್ = {ಆಲೂಗಡ್ಡೆ, ಹಚ್ಚೆ, ರಂಗಭೂಮಿ, ಇತರ}, ಮತ್ತು ಕೀವರ್ಡ್ ಟ್ರೀ ಅನ್ನು ಬಲಭಾಗದಲ್ಲಿ ತೋರಿಸಲಾಗಿದೆ. ಆ ಉದಾಹರಣೆಯಲ್ಲಿ, ಇಫ್ = ಪೊಟಾಟ್, ಆಗ = |tat | = 3, ಮತ್ತು ನೋಡ್ನ ವೈಫಲ್ಯದ ಕೊಂಡಿಯನ್ನು ಆ ಚಿತ್ರದಲ್ಲಿ ತೋರಿಸಲಾಗಿದೆ. ಅಹೋ-ಕೊರಾಸಿಕ್ ಅಲ್ಗಾರಿದಮ್ನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸುಧಾರಿಸಲು ವೈಫಲ್ಯದ ಸಂಪರ್ಕವನ್ನು ಸ್ಥಾಪಿಸುವುದು ಪ್ರಮುಖವಾಗಿದೆ. ಮೂಲ ಬಹುಪದದ ಸಮಯವನ್ನು ಹುಡುಕುವ ರೇಖೀಯ ಸಮಯಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಲು ಇದನ್ನು ಬಳಸಬಹುದು. ಆದ್ದರಿಂದ, ಕೀವರ್ಡ್ ಟ್ರೀ ಸಿದ್ಧಾಂತದ ತಿರುಳು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಕೀವರ್ಡ್ ಟ್ರೀನ ಎಲ್ಲಾ ವೈಫಲ್ಯದ ಕೊಂಡಿಗಳನ್ನು (ಅಂದರೆ ಎಲ್ಲವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು) ಕಂಡುಹಿಡಿಯುವುದು. ರೂಟ್ ನೋಡ್ನಿಂದ ಕಡಿಮೆ ಅಥವಾ ಸಮಾನ ಅಂತರವನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ನೋಡ್ಗಳನ್ನು ಕಾಣಬಹುದು ಎಂದು ಊಹಿಸಲಾಗಿದೆ. ರೂಟ್ ನೋಡ್ನಿಂದ ದೂರವು + 1 ಆಗಿರುವ ನೋಡ್ ಅನ್ನು ನಂತರ ಹುಡುಕಬಹುದು. ಇದರ ಮೂಲ ನೋಡ್ ಆಗಿದೆ, ಮತ್ತು ನೋಡ್ ಮತ್ತು ಪ್ರತಿನಿಧಿಸುವ ಅಕ್ಷರವು ಆಗಿದೆ. (1): ನೋಡ್ನ ಮುಂದಿನ ಅಕ್ಷರವು ಇದ್ದರೆ, ಈ ಅಂಚಿನ ಇತರ ನೋಡ್ ಅನ್ನು, ಮತ್ತು = ಎಂದು ಹೊಂದಿಸಬಹುದು. (2): ಎಲ್ಲಾ ಅಕ್ಷರಗಳು ಮತ್ತು ಅದರ ಚೈಲ್ಡ್ ನೋಡ್ಗಳ ನಡುವಿನ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಹುಡುಕದಿದ್ದರೆ, ಅದು ಪ್ಲಸ್ ನ ಪ್ರತ್ಯಯವಾಗಿರುತ್ತದೆ. ಈ ಪ್ರತ್ಯಯವು ಮೂಲ ನೋಡ್ನಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಸ್ಟ್ರಿಂಗ್ಗೆ ಹೊಂದಿಕೆಯಾಗುವುದರಿಂದ (ಪೂರ್ವಪ್ರತ್ಯಯಕ್ಕೆ ಹೋಲುತ್ತದೆ), ನಂತರದದನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು ಅಥವಾ ಕಂಡುಹಿಡಿಯಲಾಗುವುದಿಲ್ಲ. ಇಲ್ಲದಿದ್ದರೆ, ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ರೂಟ್ ನೋಡ್ ದೊರೆಯುವವರೆಗೆ ಮುಂದುವರಿಸಬಹುದು. ಅಹೋ-ಕೋರಾಸಿಕ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಕೀವರ್ಡ್ ಟ್ರೀಯಲ್ಲಿ ಎಲ್ಲಾ ವೈಫಲ್ಯದ ಕೊಂಡಿಗಳನ್ನು ಸ್ಥಾಪಿಸಿದ ನಂತರ, ಅಹೋ-ಕೋರಾಸಿಕ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಎಲ್ಲಾ (i = 1,2,., z) ಸ್ಥಳಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬಳಸಲಾಗುತ್ತದೆ. ಈ ಹಂತದಲ್ಲಿ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O (m + k) ಆಗಿದೆ. ಎಂ. ಎಸ್. ಎ., ಡಿ. ಎನ್. ಎ., ಆರ್. ಎನ್. ಎ. ಮತ್ತು ಪ್ರೋಟೀನ್ಗಳಲ್ಲಿ, ಅನುಕ್ರಮಗಳನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಉತ್ಪಾದಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಅವು ವಿಕಸನೀಯ ಸಂಬಂಧವನ್ನು ಹೊಂದಿವೆ ಎಂದು ಭಾವಿಸಲಾಗಿದೆ. ಆರ್ಎನ್ಎ, ಡಿಎನ್ಎ ಮತ್ತು ವಿಕಸನೀಯ ಕುಟುಂಬಗಳ ಅನುಕ್ರಮಗಳ ರಚಿತ ನಕ್ಷೆಗಳನ್ನು ಹೋಲಿಸುವ ಮೂಲಕ, ಜನರು ಪ್ರೋಟೀನ್ಗಳ ಸಂರಕ್ಷಣೆಯನ್ನು ನಿರ್ಣಯಿಸಬಹುದು ಮತ್ತು ವಿಕಸನೀಯ ಅನುಕ್ರಮಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸಗಳನ್ನು ಹೋಲಿಸುವ ಮೂಲಕ ಕ್ರಿಯಾತ್ಮಕ ಜೀನ್ ಕ್ಷೇತ್ರಗಳನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು. ಸಾಮಾನ್ಯವಾಗಿ, ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ಗಳು ಮತ್ತು ಟ್ರೀ ಅಲೈನ್ಮೆಂಟ್ ಗ್ರಾಫ್ಗಳನ್ನು ಸಹ ಅಳವಡಿಸಿಕೊಳ್ಳಲಾಗುತ್ತದೆ. ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ ಸಾಮಾನ್ಯವಾಗಿ, ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ಗಳು ಪುನರಾವರ್ತಿತ ಕಾರ್ಯತಂತ್ರವನ್ನು ಅವಲಂಬಿಸಿವೆ, ಅಂದರೆ ಹೋಲಿಕೆ ವಿಧಾನದ ಆಧಾರದ ಮೇಲೆ, ಪುನರಾವರ್ತಿತ ಪ್ರಕ್ರಿಯೆಯಿಂದ ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆಯ ಫಲಿತಾಂಶಗಳನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿಸುತ್ತದೆ. ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಕಣ ಸಮೂಹ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಲು ಡೇವಿ ಎಮ್. ಪ್ರಸ್ತಾಪಿಸಿದರು; ಇಕೆಡಾ ತಕಾಹಿರೋ ಎ * ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಆಧರಿಸಿದ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು; ಇ. ಬಿರ್ನಿ ಮೊದಲು ಬಹು ಅನುಕ್ರಮ ಜೋಡಣೆ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಗುಪ್ತ ಮಾರ್ಕೋವ್ ಮಾದರಿಯನ್ನು ಬಳಸಿ ಪ್ರಸ್ತಾಪಿಸಿದರು; ಮತ್ತು ಇತರ ಅನೇಕ ಜೀವಶಾಸ್ತ್ರಜ್ಞರು ಅದನ್ನು ಪರಿಹರಿಸಲು ಜೆನೆಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸುತ್ತಾರೆ. ಈ ಎಲ್ಲಾ ಕ್ರಮಾವಳಿಗಳು ಸಾಮಾನ್ಯವಾಗಿ ದೃಢವಾಗಿರುತ್ತವೆ ಮತ್ತು ಅನುಕ್ರಮಗಳ ಸಂಖ್ಯೆಗೆ ಸೂಕ್ಷ್ಮವಾಗಿರುವುದಿಲ್ಲ, ಆದರೆ ಅವು ನ್ಯೂನತೆಗಳನ್ನು ಸಹ ಹೊಂದಿವೆ. ಉದಾಹರಣೆಗೆ, ಪಾರ್ಟಿಕಲ್ ಸ್ವಾರ್ಮ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಅಲ್ಗಾರಿದಮ್ನ ಫಲಿತಾಂಶಗಳು ಅಸ್ಥಿರವಾಗಿರುತ್ತವೆ ಮತ್ತು ಅದರ ಅರ್ಹತೆಗಳು ಯಾದೃಚ್ಛಿಕ ಸಂಖ್ಯೆಗಳ ಆಯ್ಕೆಯನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ, ಎ * ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ನ ಚಾಲನೆಯ ಸಮಯವು ತುಂಬಾ ಉದ್ದವಾಗಿದೆ, ಮತ್ತು ಜೆನೆಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸ್ಥಳೀಯ ಅತ್ಯುತ್ತಮ ಕ್ರಮಕ್ಕೆ ಸೇರಿಸುವುದು ಸುಲಭ. ಮರದ ಜೋಡಣೆಯ ರೇಖಾಚಿತ್ರ ಸ್ಥೂಲವಾಗಿ, ಮರದ ಜೋಡಣೆಯ ರೇಖಾಚಿತ್ರವು ಮರಗಳನ್ನು ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಜೋಡಿಸುವ ಮತ್ತು ಅಂತಿಮವಾಗಿ ಅಂಕಿಅಂಶಗಳನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲು ಅವುಗಳನ್ನು ಸಂಶ್ಲೇಷಿಸುವ ಗುರಿಯನ್ನು ಹೊಂದಿದೆ. ಜೀವಶಾಸ್ತ್ರದಲ್ಲಿ, ಮರದ ಜೋಡಣೆಯ ರೇಖಾಚಿತ್ರಗಳನ್ನು (ಟಿ. ಎ. ಜಿ. ಗಳು) ಮರಗಳ ಗುಂಪಿನಿಂದ ವಿಕಸನೀಯ ಘರ್ಷಣೆಗಳು ಅಥವಾ ಅತಿಕ್ರಮಿಸುವ ವರ್ಗಗಳನ್ನು ತೆಗೆದುಹಾಕಲು ಬಳಸಲಾಗುತ್ತದೆ ಮತ್ತು ನಂತರ ಅನಿಶ್ಚಿತತೆ ಮತ್ತು ಸಂಘರ್ಷವನ್ನು ಅನ್ವೇಷಿಸಲು ಪ್ರಶ್ನಿಸಬಹುದು. ಜೋಡಣೆ, ಸಂಶ್ಲೇಷಣೆ ಮತ್ತು ವಿಶ್ಲೇಷಣೆಯ ವಿಧಾನಗಳನ್ನು ಸಂಯೋಜಿಸುವ ಮೂಲಕ, ಟಿಎಜಿ ವ್ಯಾಪಕ ಶ್ರೇಣಿಯ ಅನುಕ್ರಮಗಳಿಂದ ಪಡೆದ ಸಂಘರ್ಷದ ಸಂಬಂಧಗಳು ಮತ್ತು ಭಾಗಶಃ ಅತಿಕ್ರಮಿಸುವ ಟ್ಯಾಕ್ಸನ್ ಸೆಟ್ಗಳನ್ನು ಪರಿಹರಿಸುವ ಗುರಿಯನ್ನು ಹೊಂದಿದೆ. ಅಲ್ಲದೆ, ಮರದ ಜೋಡಣೆಯ ರೇಖಾಚಿತ್ರವು ಸೂಪರ್ಟ್ರೀ ಮತ್ತು ಗ್ರಾಫ್ಟಿಂಗ್ ವ್ಯಾಯಾಮಗಳಿಗೆ ಮೂಲಭೂತ ವಿಧಾನವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ, ಇವುಗಳನ್ನು ಬೆರ್ರಿಯವರು ಸೂಪರ್ಟ್ರೀಗಳನ್ನು ನಿರ್ಮಿಸಲು ಯಶಸ್ವಿಯಾಗಿ ಪರೀಕ್ಷಿಸಿದ್ದಾರೆ. ಮರಗಳಿಂದ ಗ್ರಾಫ್ಗೆ ಪರಿವರ್ತನೆಯು ಅವುಗಳ ಮೂಲ ಮರಗಳಿಂದ ಒಂದೇ ರೀತಿಯ ನೋಡ್ಗಳು ಮತ್ತು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವುದರಿಂದ, ಟಿಎಜಿಗಳು ಹೆಚ್ಚಿನ ವಿಶ್ಲೇಷಣೆಗಾಗಿ ಮೂಲ ಮೂಲ ಮರಗಳ ಹೊರತೆಗೆಯುವಿಕೆಯನ್ನು ಸಹ ಒದಗಿಸಬಹುದು. ಟಿ. ಎ. ಜಿ. ಯು ಜೋಡಿಸಲಾದ ಮರಗಳ ಸಂಯೋಜನೆಯಾಗಿದೆ. ಇದು ವಿಕಸನೀಯ ಸಂಬಂಧದ ವಿರುದ್ಧವಾದ ಊಹೆಗಳನ್ನು ಸಂಗ್ರಹಿಸಬಹುದು ಮತ್ತು ವಿಕಸನೀಯ ಊಹೆಗಳನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲು ಮೂಲ ಮರಗಳನ್ನು ಸಂಶ್ಲೇಷಿಸಬಹುದು. ಆದ್ದರಿಂದ, ಇತರ ಜೋಡಣೆಯ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಇದು ಒಂದು ಮೂಲಭೂತ ವಿಧಾನವಾಗಿದೆ. ಸಾಮಾನ್ಯೀಕೃತ ಮರದ ಜೋಡಣೆಯ ಉಲ್ಲೇಖಗಳು ಕಂಪ್ಯೂಟೇಶನಲ್ ಫೈಲೋಜೆನೆಟಿಕ್ಸ್ ಅನ್ನು ಸಹ ನೋಡಿ.