Tối ưu hóa tính toán độ cong của ADN trong nghiên cứu

Luận văn thạc sĩ nghiên cứu optimation du calcul de la courbure d adn, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực .

• Người hướng dẫn: Mme. Debled-Rennesson
• Trường học: Institut de Francophonie pour l’Informatique
• Chuyên ngành: Informatique
• Đề tài: Tối ưu hóa tính toán độ cong của ADN
• Loại tài liệu: mémoire
• Năm xuất bản: 2020
• Địa điểm: Nancy

Tóm tắt

I. Tổng Quan Về Độ Cong ADN Tại Sao Lại Quan Trọng

Nghiên cứu độ cong ADN đóng vai trò quan trọng trong việc hiểu rõ các quá trình sinh học cơ bản. Sự phát triển của tin học và ứng dụng của nó trong hình học đã tạo ra những tiến bộ đáng kể trong lĩnh vực này. Các kiến thức toán học, đặc biệt là hình học Euclid, có thể được điều chỉnh để áp dụng cho dữ liệu rời rạc, mở ra khả năng mới để phân tích cấu trúc ADN. Các thuộc tính chung giữa hình học Euclid và các không gian khác cho phép chúng ta sử dụng các khái niệm hình học để nghiên cứu biến dạng ADN một cách hiệu quả hơn. Hình học rời rạc, kết hợp các phương pháp lý thuyết từ tô pô, hình học số học, đồ thị và tổ hợp, cung cấp một nền tảng vững chắc cho việc phân tích và mô hình hóa độ cong ADN. Nhiều khám phá quan trọng trong lĩnh vực này đã được thực hiện nhờ cách tiếp cận này. Các phương pháp tính toán độ cong ADN đang ngày càng trở nên quan trọng trong nghiên cứu biểu hiện gen và tương tác protein-ADN.

1.1. Ứng Dụng Của Hình Học Rời Rạc Trong Nghiên Cứu ADN

Hình học rời rạc cung cấp các công cụ mạnh mẽ để phân tích hình học ADN. Nó cho phép chúng ta áp dụng các khái niệm hình học Euclid vào các dữ liệu rời rạc, vốn là bản chất của dữ liệu trình tự ADN. Phương pháp này đặc biệt hữu ích trong việc nghiên cứu tương tác protein-ADN, nơi hình dạng và độ cong ADN đóng vai trò quan trọng. Việc áp dụng hình học số học giúp phân tích mật độ ADN và sự ổn định của ADN một cách chi tiết. Điều này có ý nghĩa lớn trong việc hiểu các cơ chế sửa chữa ADN và sao chép ADN.

1.2. Tầm Quan Trọng Của Độ Cong ADN Trong Sinh Học Phân Tử

Độ cong ADN ảnh hưởng trực tiếp đến nhiều quá trình sinh học quan trọng. Nó đóng vai trò quyết định trong việc biểu hiện gen, tương tác protein-ADN, và sự ổn định của ADN. Ví dụ, các protein có thể nhận diện các khu vực ADN có độ cong đặc biệt và liên kết vào đó để điều chỉnh quá trình phiên mã. Độ cong ADN cũng ảnh hưởng đến khả năng tiếp cận của các enzyme sửa chữa ADN, do đó ảnh hưởng đến tính toàn vẹn của bộ gen. Hiểu rõ ảnh hưởng của độ cong ADN là rất quan trọng để giải mã các cơ chế điều hòa gen và phát triển các liệu pháp gen hiệu quả.

II. Thách Thức Trong Tính Toán Độ Cong ADN Điểm Nghẽn

Việc tính toán độ cong ADN gặp phải một số thách thức đáng kể. Các phương pháp hiện tại thường dựa trên việc phân đoạn đường cong, nhưng việc này có thể dẫn đến mất thông tin quan trọng. Hơn nữa, việc áp dụng trực tiếp các phương pháp hình học liên tục vào dữ liệu ADN rời rạc không phải lúc nào cũng chính xác. Nhóm nghiên cứu ADAGE tại LORIA đang nỗ lực giải quyết những thách thức này bằng cách phát triển các thuật toán tối ưu hóa để tính toán độ cong ADN. Các thuật toán này dựa trên công trình trước đây của Debled-Rennesson về phân đoạn đường cong và tiếp tuyến, nhưng mở rộng để áp dụng cho các đường cong ADN. Mục tiêu là phát triển một thuật toán có độ phức tạp tính toán thấp hơn và có thể xử lý các đường cong không liên tục.

2.1. Hạn Chế Của Các Phương Pháp Phân Đoạn Đường Cong Truyền Thống

Các phương pháp phân đoạn đường cong truyền thống có thể dẫn đến mất thông tin quan trọng do quá trình rời rạc hóa. Việc lựa chọn kích thước phân đoạn cũng có thể ảnh hưởng đến độ chính xác của kết quả. Ngoài ra, các phương pháp này thường không hiệu quả trong việc xử lý các đường cong không liên tục, vốn phổ biến trong mô hình hóa độ cong ADN. Do đó, cần có các phương pháp mới để tính toán độ cong ADN một cách chính xác và hiệu quả.

2.2. Vấn Đề Độ Phức Tạp Tính Toán Của Các Thuật Toán

Một thách thức khác là độ phức tạp tính toán của các thuật toán tính toán độ cong ADN. Các thuật toán hiện tại có thể yêu cầu một lượng lớn tài nguyên tính toán, đặc biệt là khi xử lý các trình tự ADN lớn. Điều này hạn chế khả năng áp dụng của chúng trong các nghiên cứu quy mô lớn. Do đó, cần phát triển các thuật toán tối ưu hóa độ cong ADN với độ phức tạp tính toán thấp hơn.

2.3. Khó khăn khi áp dụng lý thuyết Hình học Euclid vào dữ liệu ADN

Việc áp dụng trực tiếp các phương pháp hình học liên tục của Euclid vào dữ liệu ADN rời rạc không phải lúc nào cũng chính xác. Dữ liệu ADN là rời rạc bởi nó là trình tự của các base. Vì vậy cần có những chỉnh sửa hoặc phương pháp luận thích hợp để có thể sử dụng lý thuyết này.

III. Phương Pháp Tính Toán Độ Cong ADN Tối Ưu Hướng Dẫn Chi Tiết

Phương pháp tính toán độ cong ADN tối ưu bao gồm một số bước chính. Đầu tiên, dữ liệu ADN được tiền xử lý để loại bỏ nhiễu và chuẩn hóa. Tiếp theo, một thuật toán phân đoạn đường cong được áp dụng để chia ADN thành các đoạn nhỏ hơn. Sau đó, độ cong của mỗi đoạn được tính toán bằng cách sử dụng một phương pháp hình học phù hợp. Cuối cùng, các kết quả được tổng hợp để tạo ra một bản đồ độ cong ADN hoàn chỉnh. Nhóm nghiên cứu ADAGE đang phát triển một thuật toán mới dựa trên khái niệm về các đoạn mờ để cải thiện độ chính xác và hiệu quả của phương pháp này. Theo Debled-Rennesson, đoạn mờ cho phép mô hình hóa độ cong ADN tốt hơn so với các phương pháp phân đoạn truyền thống.

3.1. Tiền Xử Lý Dữ Liệu ADN Bước Chuẩn Bị Quan Trọng

Tiền xử lý dữ liệu ADN là một bước quan trọng để đảm bảo độ chính xác của các tính toán độ cong ADN. Bước này bao gồm việc loại bỏ nhiễu từ các nguồn khác nhau, chẳng hạn như lỗi giải trình tự hoặc các artefakt thực nghiệm. Nó cũng bao gồm việc chuẩn hóa dữ liệu để đảm bảo rằng các đoạn ADN khác nhau có thể so sánh được. Các phương pháp tiền xử lý phổ biến bao gồm lọc, cắt tỉa và điều chỉnh độ dài trình tự.

3.2. Sử Dụng Đoạn Mờ Để Phân Đoạn Đường Cong ADN Ưu Điểm

Việc sử dụng các đoạn mờ để phân đoạn đường cong ADN có một số ưu điểm so với các phương pháp phân đoạn truyền thống. Các đoạn mờ cho phép biểu diễn chính xác hơn hình học ADN, đặc biệt là trong các khu vực có độ cong cao. Chúng cũng ít nhạy cảm hơn với nhiễu và các artefakt thực nghiệm. Các đoạn mờ cũng có thể được sử dụng để dự đoán độ cong ADN trong các khu vực chưa được giải trình tự.

3.3. Áp dụng các phương pháp hình học phù hợp để tính toán

Sử dụng các phương pháp hình học như đường cong Bézier, spline,... để tính toán độ cong trên các đoạn ADN đã chia. Việc lựa chọn các phương pháp phụ thuộc vào mức độ phức tạp của cấu trúc ADN và các yêu cầu về độ chính xác.

IV. Bí Quyết Tối Ưu Thuật Toán Tính Toán Độ Cong ADN Nhanh Chóng

Để tối ưu hóa thuật toán tính toán độ cong ADN, có một số kỹ thuật có thể được áp dụng. Đầu tiên, có thể sử dụng các thuật toán song song để giảm thời gian tính toán. Tiếp theo, có thể sử dụng các cấu trúc dữ liệu hiệu quả để lưu trữ và truy xuất dữ liệu ADN. Cuối cùng, có thể sử dụng các phương pháp xấp xỉ để giảm độ phức tạp tính toán của thuật toán. Debled-Rennesson đã đề xuất một số kỹ thuật để giảm độ phức tạp tính toán của thuật toán phân đoạn đường cong của họ. Các kỹ thuật này bao gồm việc sử dụng các đường bao lồi để xấp xỉ hình dạng của ADN và sử dụng các thuật toán tìm kiếm hiệu quả để xác định các đoạn ADN.

4.1. Áp Dụng Thuật Toán Song Song Để Giảm Thời Gian Tính Toán

Việc áp dụng các thuật toán song song có thể giảm đáng kể thời gian tính toán cho tính toán độ cong ADN. Điều này đặc biệt quan trọng khi xử lý các trình tự ADN lớn. Các thuật toán song song có thể được triển khai trên nhiều lõi CPU hoặc trên các hệ thống tính toán phân tán.

4.2. Sử Dụng Cấu Trúc Dữ Liệu Hiệu Quả Để Lưu Trữ Dữ Liệu ADN

Việc sử dụng các cấu trúc dữ liệu hiệu quả để lưu trữ và truy xuất dữ liệu ADN có thể cải thiện đáng kể hiệu suất của thuật toán tính toán độ cong ADN. Các cấu trúc dữ liệu phổ biến bao gồm cây và đồ thị. Các cấu trúc dữ liệu này cho phép truy xuất dữ liệu nhanh chóng và hiệu quả, đặc biệt là khi xử lý các trình tự ADN lớn.

V. Ứng Dụng Thực Tế Của Tính Toán Độ Cong ADN Nghiên Cứu

Tính toán độ cong ADN có nhiều ứng dụng thực tế quan trọng. Nó có thể được sử dụng để nghiên cứu tương tác protein-ADN, biểu hiện gen, và sửa chữa ADN. Nó cũng có thể được sử dụng để phát triển các liệu pháp gen mới. Ví dụ, độ cong ADN có thể được sử dụng để thiết kế các protein liên kết ADN có thể điều chỉnh quá trình phiên mã hoặc sửa chữa các đột biến gen. Các nghiên cứu của Frank Rappaport DEA đã chỉ ra rằng tính toán độ cong ADN có thể giúp hiểu rõ hơn về cấu trúc và chức năng của ADN.

5.1. Nghiên Cứu Tương Tác Protein ADN Bằng Tính Toán Độ Cong

Độ cong ADN đóng vai trò quan trọng trong tương tác protein-ADN. Nhiều protein liên kết ADN nhận diện các khu vực ADN có độ cong đặc biệt. Tính toán độ cong ADN có thể giúp xác định các vị trí liên kết protein tiềm năng và hiểu rõ hơn về cơ chế điều hòa gen.

5.2. Ứng Dụng Trong Thiết Kế Liệu Pháp Gen Mới

Tính toán độ cong ADN có thể được sử dụng để thiết kế các liệu pháp gen mới. Ví dụ, độ cong ADN có thể được sử dụng để thiết kế các protein liên kết ADN có thể điều chỉnh quá trình phiên mã hoặc sửa chữa các đột biến gen. Điều này mở ra những khả năng mới để điều trị các bệnh di truyền và ung thư.

VI. Tương Lai Của Tính Toán Độ Cong ADN Hướng Phát Triển

Tương lai của tính toán độ cong ADN hứa hẹn nhiều tiềm năng. Các nhà nghiên cứu đang tiếp tục phát triển các thuật toán mới để cải thiện độ chính xác và hiệu quả của các tính toán độ cong ADN. Họ cũng đang khám phá các ứng dụng mới của tính toán độ cong ADN trong các lĩnh vực như y học cá nhân và công nghệ sinh học. Sự kết hợp giữa hình học rời rạc và sinh học phân tử sẽ tiếp tục mang lại những khám phá quan trọng về cấu trúc và chức năng của ADN.

6.1. Phát Triển Các Thuật Toán Mới Với Độ Chính Xác Cao Hơn

Một trong những hướng phát triển quan trọng nhất là phát triển các thuật toán mới với độ chính xác cao hơn. Các thuật toán này sẽ cần phải có khả năng xử lý các đường cong ADN phức tạp và ít nhạy cảm hơn với nhiễu.

6.2. Khám Phá Các Ứng Dụng Mới Trong Y Học Cá Nhân

Tính toán độ cong ADN có thể có nhiều ứng dụng trong y học cá nhân. Ví dụ, nó có thể được sử dụng để dự đoán nguy cơ mắc bệnh di truyền hoặc để thiết kế các liệu pháp gen phù hợp với từng cá nhân.

Trích đoạn nội dung tài liệu

Institut de la Francophonie pour l’Informatique Optimisation du calcul de la courbure d’ADN MEMOIRE soutenu le. pour l’obtention du DEPA de l'Institut de la Francophonie pour |’Informatique (Spécialité Informatique) par Thanh Phuong NGUYEN Composition du jury FEincadrant : Isabelle DEBLED-RENNESSON Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503 Remerciements Tout d’abord, je souhaite remercier vivement mon responsable de stage, Mme. Isabelle DEBLED-RENNESSON pour m’avoir aidé et guidé tout au long de mon stage, d’avoir évoqué ma passion pour la géométrie discréte et d’avoir me donné des conseils précieux pendant le stage. Je souhaite aussi remercier M.

Fabien FESCHET (LLACD) d’avoir fourni son programme et m’avoir permis de l’utiliser dans mon travail ainsi qu’avoir répondu aux questions concernant son programme. Je voudrais remercier Mme Jocelyne ROUYER (ADAGE) qui me donne son évaluation sur mon travail pendant le stage. Je voudrais remercier M. Jean-Luc REMY (ADAGE) d’avoir lu mon mémoire et d’avoir donné des commentaires prestigieux.

Je tiens 4 remercier tous les professeurs de l’IFI qui m’ont enseigné les connaissances professionnelles pendant mes études de master de recherche. Je tiens 4 remercier aussi tous les membres de l’équipe ADAGE, tout particuliérement Sylvain BLONDEAU qui a fait des remarques sur le programme, pour leur amitié et leurs nombreux conseils. Enfin, je remercie tout spécialement mes parents qui m’ont toujours encouragé dans mes études. Table des matiéres Introduction 1 1 Motivation.

ee 1 2 Présentation du probléme .0000 epee eee eee 1 3 Structure durapport .22 ee ee 2 Chapitre 1 Notions 3 1.2 Segment Houen3ÙD.002022 ee ee 9 15 Courbed’ADN .1 Structure de molécule d’ADN .2 Modéle dela courbe d’ADN. 2220088 e 10 Chapitre 2 Etat de lˆart 11 2.2 Segmentation de la courbe discréte en segments flous. La courbure et la tangente. - HQ HH HH ko 14 2.

co Q ee ee 14 "B5 NN. 15 il ill Chapitre 3 Etude théorique 17 3.1 Etude de l’algorithme de reconnaissance d’un segment flou.2 Les propriếtés de lenveloppe convexe.4 Conception des algorlthmes.Ặ Q Q SH HQ HH Ra 21 3.2 Etude de l’algorithme de calcul de la tangente et dela courbure.1 Algorithme de calcul de la tangente.2 Adaptation de lalgorithme de Melkman .3 Calcul de la courbure en chaque point .1 Calcul de la courbure en chaque point d’une courbe 2D .2 Calcul de la courbure en chaque point d’une courbe 3D .4 Calcul d’un segment flou a4 Pétape suivante .2 Calcul d’un segment flou 4 ’étape suivante. 200202002 ee ee eee 32 3.002 2 eee ee eee 34 Chapitre 4 Expérimentation 36 4.1 Présentation du programme. Ặ HQ HQ HH ko 36 4.1 Les paramétres d’entrée.

- HQ HH Ha 36 4.1 Calcul dun segment Ñou avec une épalsseur donnée.2 Calcul de la courbure en chaque point .3 Calcul de la tangente en chaque point .3 Application aux courbesd’ADN.2020 00220 eee ee ee 42 Conclusion 44 Bibliographie 45 Table des figures 1.1 2 types de connexitéen 2D .000 eee ee ee C2 1.2 3 types de connexitéen 3D .0 2200 eee ee ee nh 1.3 Une droite discréte en 2D : D(3,—-5,-3,2).4 Droites d’appui et points d’appui .--0 20-0022 ee ee ee 1.5 Les droites ont des connexités différentes .6 Une droite discréteen 3D .0002 ee ee CON 1.7 Calcul de lacourbure3D .0002 eee ee eee 1.8 Structure de VADN.9 Modélisation de 1 ADN avec modéle tubulaire (modélisation obtenue a l’aide du logiciel CURVATURE).1 Transformation des cas sommet-sommet vers les cas aréte-sommet .2 Cas ott M;, M2 se trouvent sur le méme demi-plan dont le bord est la hauteur de Yenveloppe convexe pour Sf.3 Calcul de la largeUT. - HQ HQ HQ HH ee ee.4 Calcul dela hauteur .0002 eee ee ee 20 3.9 Calcul de la courbure d’ordre 2 en un point T.6 Segment flou originel .7 Aprés avoir effectué l’étape 2, X coincide avec A;. Dans l’étape 6, on cherche des candidats pour X dans la zone marquée entre A; etR .8 Avant létape 3, X coincide avec A, puis X coincide avec Ơi ; avant létape 4, Y coincide avec Y, puis Y coincide avec By.10 Chercher et trouver les candidats pour X et Y. Aprés l’étape 6, X est assigné a M dans la premiére zone marquée.

Aprés l’étape 7, Y est assigné 4 N dans la deuxiéme zone marquée.11 Avant l’étape 9, X coincide avec M, Y coicide avec Y. Aprés cette étape, Z est assignéaP .1 Les courbures d’extrait d’un cercle 3D dont le rayon est 10.2 Les courbures d’extrait 4 partir d’une courbe en spirale dont le rayon est 10 .3 Les courbures d’extrait 4 partir d’autre courbe en spirale dont le rayon est 10 .4 Segmentation d’une courbe discréte en segments flous.5 Les courbures obtenues en tous les points d’une courbe en 3D .6 Les courbures extraites 4 partir des formes différentes de la courbe d’ADN du virus E-coli. Lépalsseur d'extralt est toujours 3. 1V LISTE DES ALGORITHMES V Liste des Algorithmes Segmentation des courbes 8-connexes en segments flous.

13 Reconnaissance incrémentale d’un segment flou avec ’épaisseurv. 14 WN Algorithme de reconnaissance de la tangente au point central. 16 Calculer la largeur 4 chaque étape .022002 eee 22 FR Calculer la hauteur 4 chaque étape.-0- 20220-0207 | 23 Oo Construire la droite englobante optimale pour un segment flou. 24 Calculer la tangente 4 la courbe H au point P.

25 CoN Déterminer l’enveloppe convexe d’un polygone simple. 26 Lalgorithme adapté de Melkman. Ặ QẶ HQ Q HQ 27 ke © Reconnaissance dˆun segment fÑou 3D d'épalsseUr0. 28 Pre & Calcul la courbure en chaque point de la courbe discrète 3D.

28 or Déterminer le segment Ñou à étape suivanie.Ặ Ặ QẶ Q QẶ 35 Introduction 1 Motivation Avec le développement de l’imagerie informatique et son application dans des contextes de plus en plus diversifiés, la géométrie discréte a des grands progrés dans des années derniéres. Ce domaine, qui est basé sur des connaissances mathématiques, vise 4 étudier des objets discrets. Ces objets se composent d’un ensemble dénombrable des points entiers. Alors, les connaissances de la géométrie euclidienne qui s’adaptent aux objets continus ne peuvent pas s’appliquer sur ces objets.

Normalement, les objets discrets ont peu de propriétés communes par rapport aux leurs homologues continus. Les résultats les plus élémentaires de la géométrie euclidienne ne sont pas vérifiés dans des espaces discrets. En fait, la géométrie discréte reprend des notions familiéres de la géométrie euclidienne en développant des théorémes spécifiques au type d’espace et d’objet discret. La géométrie discréte regroupe des approches théoriques différentes telles que : topologie discréte, géométrie arithmétique, théorie des graphes et combinatoire.

Parmi ces approches, l’approche de géométrie arithmétique qui lie les propriétés des objets discrets a celle des nombres entiers est V’approche principale puisqu’elle s’adapte mieux au calcul informatique. Plusieurs des résultats fondamentaux de ce domaine ont été découverts grace a cette approche. C’est aussi la méthode pour notre travail de stage. 2 Présentation du probléme L’équipe ADAGE(Algorithmique Discréte et ses Applications 4 la GEnomique) du laboratoire LORIA (Laboratoire LOrraine de Recherche en Informatique et ses Applications) étudie l’algo- rithmique discréte et ses applications au traitement des informations génomiques.

Il y a deux thémes principaux de recherche : l’un est le traitement des textes; l'autre théme de recherche est la géométrie discréte. Du cété pratique, le développement des logiciels qui permettent de les traiter est aussi important. Ce stage est effectué dans cette équipe dans le contexte de construction d’une application 4 la génomique dans le domaine de la géométrie discréte. L’objectif du stage est d’optimiser le calcul de la courbure d’ADN.

Ce travail est la continuation des travaux d’Isabelle Debled-Rennesson et al : la segmentation des segment flou de la courbe discréte [7] et [8], le calcul de la courbure et des tangentes de la courbes discréte [4]. Dans ses travaux, le calcul de la courbure et des tangentes de la courbe est basé sur la technique de segmentation des segments flous qui est présenté dans [8]. Récemment, Debled-Rennesson et al. présentent un algorithme optimal [5] pour segmenter des segments flous de la courbe.

Alors, dans le cadre de ce stage, nous visons 4 appliquer cette technique optimale pour le calcul de la courbure et des tangentes de la courbe discréte. Ceci, dans l’optique de travailler avec des courbes d’ADN. Structure du rapport 2 Dans ce stage, nous avons étudié les droites discrétes et le probléme de la segmentation en seg- ments flous d’une courbe discréte. Plusieurs des méthodes existantes sont étudiées.

Par ailleurs, nous avons proposé une nouvelle technique de segmentation des segments flous. Celle-ci peut travailler dans le cas général et est en fait une extension d’un travail [5] de Debled-Rennesson et al. En ce qui concerne ce probléme, nous proposons aussi un algorithme qui permet de calculer le segment flou de la courbe au point suivant avec une meilleure complexité par rapport au cal- cul direct. D’autre part, nous étudions et proposons un algorithme pour calculer la tangente en chaque point d’une courbe discréte.

Enfin, nous nous concentrons sur le calcul de la courbure en appliquant les techniques proposées. 3 Structure du rapport Ce rapport se compose de 4 chapitres. Le chapitre 1 présente des notions de base dans le domaine de la géométrie discréte. Le chapitre 2 donne un état de l’art sur ce probléme.

Les cha- pitre 3 et 4 vont présenter nos contributions 4 la théorie et notre implémentation expérimentale. Enfin, nous allons donner quelques conclusions de notre travail dans la partie de conclusion. Chapitre 1 Notions Dans ce chapitre, nous allons présenter les notions de base dont on a besoin pour résoudre notre probléme.1 Point discret Un point discret est l’objet discret le plus élémentaire de la géométrie discréte. Nous sa- vons qu’un point réel dans la géométrie euclidienne a des coordonnées réelles.

Par contre, les coordonnées d’un point discret sont des nombres entiers.1 Point discret en 2D Un point discret en 2D se compose de 2 coordonnées entiéres qui montrent sa position sur un plan. Il est appelé un pixel. On dit 2 points discrets connectés s’ils sont adjacents. Considérons un point discret comme un carré.

Nous avons alors 2 types de connexité pour définir les point adjacents. 4-connexe : 2 points sont connecté si ils ont un arét commune 8-connexe : 2 points sont connecté si ils ont un arét commune ou un sommet commune (a) 4 (b) & connexe connexe Fic.1 — 2 types de connexité en 2D 1.2 Point discret en 3D Un point discret en 3D contient 3 coordonnées entiéres qui déterminent sa position dans Vespace. Normalement, il est appelé un voxel. I] y a 3 types de connexité pour déterminer 2 points adjacents.

Pour la clarté, nous considérons un voxel comme une cube. Droite discréte 4 6-connexe : 2 points sont connectés si ils ont une face commune 18-connexe : 2 points sont connectés si ils ont une face commune ou une aréte commune 26-connexe : 2 points sont connectés si ils ont une face commune ou une aréte commune ou un sommet commune TT « aw Aw eA ae, aT a, | A aw py y | AT (a) 6-connexe (b) 18- (c) 26- connexe connexe Fic.2 — 3 types de connexité en 3D 1.2 Droite discréte La droite discréte est un résultat principal de la géométrie discréte. A partir de cet objet, plu- sieurs des objets complexes sont construits. D’ailleurs, la reconnaissance des segments de droites a nombreux applications dans les domaines comme le traitement d’images, la reconnaissance des formes, l’algorithmique graphique.

Alors, la droite discréte a intéressé plusieurs chercheurs dans les années derniéres.