Mohamed Abdelmoula
email: mohamedeid@gazi.edu.tr

Alejandro Montón Zarazaga

Gökhan Küçüktürk

Francis Maury
email: francis.maury@ensiacet.fr

David Grossin
email: david.grossin@ensiacet.fr

Marc Ferrato
email: marc.ferrato@mersen.com

Marco Mandolini

Paolo Cicconi

Patrick Pradel

Mohamed Abdelmou

Alejandro Montón Zarazaga
email: alejandro.montonzarazaga@ensiacet.fr

Scanning Strategy Investigation for Direct Powder Bed Selective Laser Processing of Silicon Carbide Ceramic

Keywords: selective laser processing, SiC, simulation, scanning strategy

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Silicon carbide (SiC) is considered one of the most important ceramic materials due to its superior properties, advantages, and wide application in many fields [START_REF] Cui | Multi-Functional SiC/Al Composites for Aerospace Applications[END_REF][START_REF] Hunter | Development of SiC-Based Gas Sensors for Aerospace Applications[END_REF]. SiC advantages are wear resistance, good electrical conductivity, high heat transfer capacity, and thermal stability in harsh environments [START_REF] Yonenaga | Thermo-Mechanical Stability of Wide-Bandgap Semiconductors: High Temperature Hardness of SiC, AlN, GaN, ZnO and ZnSe[END_REF]. Therefore, SiC has been used to improve the reliability and the efficiency of many devices used in aircraft, electric cars, and telecommunications [START_REF] Xun | Application of SiC Power Electronic Devices in Secondary Power Source for Aircraft[END_REF]. However, the unique properties of SiC make it is difficult to manufacture it without obstacles. Generally, the manufacturing of SiC can be performed using traditional techniques used with most ceramic materials, such as casting, extrusion, pressing, and injection molding [START_REF] Zhou | Casting of SiC Reinforced Metal Matrix Composites[END_REF][START_REF] Canakci | Microstructure and Properties of AA7075/Al-SiC Composites Fabricated Using Powder Metallurgy and Hot Pressing[END_REF][START_REF] Reddy | Enhanced Performance of Nano-Sized SiC Reinforced Al Metal Matrix Nanocomposites Synthesized through Microwave Sintering and Hot Extrusion Techniques[END_REF][START_REF] Rauber | Microstructure and Mechanical Properties of SiC Particle Reinforced Magnesium Composites Processed by Injection Molding[END_REF]. The use of these techniques must be followed with post-processing operations to reach the final product, and the complexity is limited.

Additive Manufacturing (AM) can offer highly complex parts with minor post-processing operations [START_REF] Ravichander | A Prediction Model for Additive Manufacturing of Inconel 718 Superalloy[END_REF][START_REF] Dalpadulo | Assessment of Computer-Aided Design Tools for Topology Optimization of Additively Manufactured Automotive Components[END_REF][START_REF] Grad | An Integrative Experimental Approach to Design Optimization and Removal Strategies of Supporting Structures Used during L-PBF of SS316L Aortic Stents[END_REF]. AM is a developing technology that can produce parts from 3D CAD models, as defined by ISO/ASTM 52900 [START_REF]ASTM International. Additive Manufacturing-General Principles-Terminology; ISO/ASTM International 52900[END_REF]. There are seven techniques of AM, namely, extrusion, binder jetting, material jetting, vat photopolymerization, direct energy deposition, sheet lamination, and powder bed selective laser processing (PBSLP). AM of SiC, using techniques such as binder jetting, extrusion, and material jetting, requires mixing another binder material with SiC powder, which needs to be removed using post-processing operations that cause shrinkage. These operations also affect the material properties and increase the production and finishing costs [START_REF] Zocca | Additive Manufacturing of SiSiC by Layerwise Slurry Deposition and Binder Jetting (LSD-Print)[END_REF][START_REF] Zhang | The Preparation of SiC-Based Ceramics by One Novel Strategy Combined 3D Printing Technology and Liquid Silicon Infiltration Process[END_REF].

PBSLP, as shown in Figure 1, is a promising manufacturing technique for the AM of SiC where it can, to some extent, overcome the previously described problems. There are two types of PBSLP: direct and in-direct. Direct-PBSLP (D-PBSLP) means that a laser source selectively sinters a pure material, while indirect-PBSLP means that another material is mixed with the powder acting as a binder and then removed by post-processing operations. The problem with SiC is that it does not have a melting phase, but it starts to decompose at approximately 2800 • C [START_REF] Kang | Thermal Decomposition of Silicon Carbide in a Plasma-Sprayed Cu/SiC Composite Deposit[END_REF]. For this reason, many authors have focused on indirect-PBSLP [START_REF] Evans | Rapid Manufacturing of Silicon Carbide Composites[END_REF][START_REF] Evans | Reaction Bonded Silicon Carbide: SFF, Process Refinement and Applications[END_REF][START_REF] Nelson | Selective Laser Sintering of Polymer-Coated Silicon Carbide Powders[END_REF][START_REF] Hon | Selective Laser Sintering of SiC/Polyamide Composites[END_REF][START_REF] Vail | Silicon Carbide Preforms for Metal Infiltration by Selective Laser Sintering TM of Polymer Encapsulated Powders[END_REF][START_REF] Xiong | Study on Dual Binders for Fabricating SiC Particulate Preforms Using Selective Laser Sintering[END_REF][START_REF] Stevinson | Support-Free Infiltration of Selective Laser Sintered (SLS) Silicon Carbide Preforms[END_REF][START_REF] Jin | The Fabrication and Mechanical Properties of SiC/SiC Composites Prepared by SLS Combined with PIP[END_REF]. Meyers et al. [START_REF] Meyers | Direct Laser Sintering of Reaction Bonded Silicon Carbide with Low Residual Silicon Content[END_REF] studied the selective laser sintering of reactionbonded SiC. They mixed SiC powder with silicon (Si) powder and then sintered the mixture using a laser source. The laser source decomposed SiC powder into silicon and carbon. The carbon reacted with the primary silicon powder (liquid) and formed SiC particles. Liu et al. [START_REF] Liu | Laser Additive Manufacturing and Homogeneous Densification of Complicated Shape SiC Ceramic Parts[END_REF] studied the improvement of SiC ceramic parts by the combination of three different processes: Laser Sintering (LS), Cold Isostatic Pressing (CIP), and Reaction Sintering (RS). They could increase the density by 2.1%. Song et al. [START_REF] Song | Performance Optimization of Complicated Structural SiC/Si Composite Ceramics Prepared by Selective Laser Sintering[END_REF] optimized the structure of a SiC/Si composite ceramic prepared by SLS. Streek et al. [START_REF] Streek | Processing of Silicon Carbide by Laser Micro Sintering[END_REF] studied the laser micro sintering of Si-SiC powder with different laser powers and focal positions. They were able to produce SiC parts with the remaining Si inside, which is considered a drawback. Löschau et al. [START_REF] Löschau | Prototyping of Complex-Shaped Parts and Tools of Si/SiC-Ceramics[END_REF] printed Si/SiC powder using the PBSLP techniques. They used different layer thickness, laser power, and scanning speed and printed different shapes of SiC parts.

From the presented literature review, it can be noted that the research rate for PBSLP of SiC is considered low, and almost all the previous studies focused on the indirect PBSLP of SiC where they used a binder material to print SiC. The process parameters (laser power, scanning speed, hatching distance, layer thickness, and scanning strategies) are a key factor for the D-PBSLP of SiC to be successful. Of all the process parameters, the scanning strategy has an essential influence on the successful PBSLP, as reported in many previous studies related to metallic materials [START_REF] Cheng | Stress and Deformation Evaluations of Scanning Strategy Effect in Selective Laser Melting[END_REF][START_REF] Song | Role of Scanning Strategy on Residual Stress Distribution in Ti-6Al-4V Alloy Prepared by Selective Laser Melting[END_REF][START_REF] Mugwagwa | Evaluation of the Impact of Scanning Strategies on Residual Stresses in Selective Laser Melting[END_REF], and its effects have not been reported yet for the PBSLP of SiC. Therefore, this study focuses on investigating the effect of scanning strategies on the D-PBSLP of SiC. Additionally, the other process parameters (laser power, sintering speed, and hatching distance) used in scanning strategy investigation should be selected appropriately.

The study starts with developing a numerical model for the proper selection of the process parameters. Then, the parameters obtained from the numerical model were used to investigate the effect of the scanning strategies. Finally, SiC complex geometry was printed using the best scanning strategy and process parameters obtained from the numerical model.

Methodology

Numerical Procedures

When the laser source starts to scan the powder using a specific laser power and sintering speed, a part of this power is absorbed by the powder, while the remaining part is back-scattered into the surroundings. The simulation of powder sintering is a complex process, and, in this study, the following assumptions were considered to make it mathematically modelled: (1) the laser heat source has uniform distribution; (2) the powder bed is a continuous medium; and (3) there are no losses due to evaporation. Additionally, it is worth mentioning that the developed model considered all the existed heat transfer mechanisms such as conduction, radiation, and convection.

Numerical Model Development

The heat transferred from the laser source to the powder bed can be described by the energy Equation (1) according to [START_REF] Moser | Multi-Layer Computational Modeling of Selective Laser Sintering Processes[END_REF]:

ρC p ∂T ∂t = ∇•(k ∇ T) + S h (1)
where ρ, C p , T, k, t, and S h represent the density, specific heat, temperature, thermal conductivity, time, and laser heat source, respectively. The laser heat source per unit volume (W/m 3 ) can be modelled according to [START_REF] Moser | Multi-Layer Computational Modeling of Selective Laser Sintering Processes[END_REF] and was assumed to have a Gaussian distribution as described by Equation ( 2):

S h = βI o α exp -2 (x -v x t) 2 + y -v y t 2 ω 2 -αz (2)
where β, I o , α, v, and R are the material absorptivity, laser intensity, absorption coefficient, scanning speed, and laser radius, respectively. The parameters x and y were used to control the laser source movement on the powder layer (scanning strategy). The absorption coefficient was estimated according to [START_REF] Groth | Absorption freier Ladungsträger in α-SiC-Kristallen[END_REF]. The laser intensity can be calculated according to [START_REF] Moser | Multi-Layer Computational Modeling of Selective Laser Sintering Processes[END_REF] as follows:

I o = 2P π ω 2 (3) ω = D b 2 × 2.146 ( 4
)
where ω is the characteristic laser radius and D b is the laser beam diameter. It is worth mentioning that a User-Defined Function (UDF) for the governing equations was developed, compiled, and solved using ANSYS FLUENT 2020R1 to model the laser source as described by Equation (2) according to [START_REF] Moser | Multi-Layer Computational Modeling of Selective Laser Sintering Processes[END_REF]. Additionally, the UDF considered the phase transformation from solid phase to sintered phase based on the sintering point of SiC where any region in the model with a temperature above the sintering point is considered a sintered region. User Defined Memory (UDM) available in ANSYS FLUENT 2020R1 was used to monitor and save the sintered region during the movement of the laser. The initial and boundary conditions used in this study are shown in Figure 2 and described by Equations ( 5) and (6):

T(x, y, z) t=0 = T O (5) -k( ∂T ∂z ) = . S h -h cov (T a -T s ) -σ Appl. Sci. 2022, 12, x FOR PEER REVIEW -k( ) = 𝑆 -ℎ (𝑇 -𝑇 ) -𝜎ℇ(𝑇 -
where 𝑇 is the ambient temperature, 𝑇 is the powder surface temp Stefan Boltzmann constant, ℇ is the emissivity, and ℎ is the conv ℇɛ The model geometry used in this study consists of three parts rep plate, the scanned powder layer, and the un-scanned powder, as show powder particles were assumed to be a continuous medium as described one layer was considered in the analysis as this is enough to predict th ters' effect. The dimensions of the model are summarized in Table 1. T ated using ANSYS Design Modeller 2020R1 and meshed using ANSYS

T 4 a -T 4 s (6)
where T a is the ambient temperature, T s is the powder surface temperature, σ is the Stefan Boltzmann constant,

-k( ) = 𝑆 -ℎ (𝑇 -𝑇 ) -𝜎ℇ(𝑇 -𝑇 ) ( 6
)
where 𝑇 is the ambient temperature, 𝑇 is the powder surface temperature, 𝜎 is the Stefan Boltzmann constant, ℇ is the emissivity, and ℎ is the convection coefficient. ℇɛ Additionally, the developed numerical model considered the SiC material properties as a function of temperature according to our previous study [START_REF] Montón | Experimental and Numerical Study for Direct Powder Bed Selective Laser Processing (Sintering/Melting) of Silicon Carbide Ceramic[END_REF] on the developed UDF.

Model Geometry and the Computational Domain

The model geometry used in this study consists of three parts representing the base plate, the scanned powder layer, and the un-scanned powder, as shown in Figure 3. The powder particles were assumed to be a continuous medium as described previously. Only one layer was considered in the analysis as this is enough to predict the process parameters' effect. The dimensions of the model are summarized in Table 1. The model was created using ANSYS Design Modeller 2020R1 and meshed using ANSYS Mesher 2020R1.

is the emissivity, and h cov is the convection coefficient. Additionally, the developed numerical model considered the SiC material properties as a function of temperature according to our previous study [START_REF] Montón | Experimental and Numerical Study for Direct Powder Bed Selective Laser Processing (Sintering/Melting) of Silicon Carbide Ceramic[END_REF] on the developed UDF.

Model Geometry and the Computational Domain

The model geometry used in this study consists of three parts representing the base plate, the scanned powder layer, and the un-scanned powder, as shown in Figure 3. The powder particles were assumed to be a continuous medium as described previously. Only one layer was considered in the analysis as this is enough to predict the process parameters' effect. The dimensions of the model are summarized in Table 1. The model was created using ANSYS Design Modeller 2020R1 and meshed using ANSYS Mesher 2020R1. ANSYS FLUENT 2020R1 was used to solve the numerical model; as described in Section 3, the laser heat source is defined using a user-defined function (UDF) containing all the laser parameters, including laser power, laser spot diameter, and sintering speed. The numerical procedure followed in this study is described by the flow chart shown in Figure 4. The computational domain (the mesh) is shown in Figure 5, where the ANSYS Mechanical Meshing Tool was used. Very fine discretization was used for the powder layer and slightly coarse was used for the unscanned powder and the baseplate. To confirm this, the results obtained from the model due to poor mesh quality were avoided. Three different levels of mesh discretization (A, B, and C) were considered in this study. The element type used in mesh discretization is hexahedral element type. The number of elements for mesh A, B, and C are 280,576, 1,000,576, and 1,540,576, respectively. The mesh density analysis was summarized in Table 2. The maximum temperature values were 2376.3 K and 2379.4 K for the last two meshes (levels) with a difference of 0.13%, which is considered low. Therefore, any discretization after level C would be valid and give accurate results, and therefore, the third level mesh size (2 µm discretization) was used in this study. Additionally, it is worth mentioning that the time step size used in this study was 0.00001 s, while the number of iterations per time step was 20 iterations/time step. These values were selected and tested to obtain more accurate results for the temperature and sintering contours. Moreover, all measurements were performed when the laser beam temperature became stable.

Experimental Procedures

Powder Characterization

Alpha-SiC powder without any additives was used for the D-PBSLP of SiC. Mersen Boostec ® supplied the powder with a purity of 98.5 % and d50 = 14 µm. Figure 6 shows the morphology of the used powder. The SEM images show that the powder has an irregular shape, which can cause problems during layer depositing because of highly developed inter-friction between particles. Therefore, initial testing was carried out, and the SiC powder could be successfully deposited with a layer of 22 µm into the powder bed.

Experimental Procedures

Powder Characterization

Alpha-SiC powder without any additives was used for the D-PBSLP of SiC. Mersen Boostec ® supplied the powder with a purity of 98.5 % and d50 = 14 µm. Figure 6 shows the morphology of the used powder. The SEM images show that the powder has an irregular shape, which can cause problems during layer depositing because of highly developed inter-friction between particles. Therefore, initial testing was carried out, and the SiC powder could be successfully deposited with a layer of 22 µm into the powder bed.

Experimental Procedures

Powder Characterization

Alpha-SiC powder without any additives was used for the D-PBSLP of SiC. Mersen Boostec ® supplied the powder with a purity of 98.5 % and d50 = 14 µm. Figure 6 shows the morphology of the used powder. The SEM images show that the powder has an irregular shape, which can cause problems during layer depositing because of highly developed inter-friction between particles. Therefore, initial testing was carried out, and the SiC powder could be successfully deposited with a layer of 22 µm into the powder bed.

Experimental Procedures

Powder Characterization

Alpha-SiC powder without any additives was used for the D-PBSLP of SiC. Mersen Boostec ® supplied the powder with a purity of 98.5 % and d50 = 14 µm. Figure 6 shows the morphology of the used powder. The SEM images show that the powder has an irregular shape, which can cause problems during layer depositing because of highly developed inter-friction between particles. Therefore, initial testing was carried out, and the SiC powder could be successfully deposited with a layer of 22 µm into the powder bed.

Experimental Procedures 2.2.1. Powder Characterization

Alpha-SiC powder without any additives was used for the D-PBSLP of SiC. Mersen Boostec ® supplied the powder with a purity of 98.5 % and d 50 = 14 µm. Figure 6 shows the morphology of the used powder. The SEM images show that the powder has an irregular shape, which can cause problems during layer depositing because of highly developed inter-friction between particles. Therefore, initial testing was carried out, and the SiC powder could be successfully deposited with a layer of 22 µm into the powder bed.

Sample Preparation and Characterization

The commercial Phoenix 3D printer manufactured by 3D Systems and equipped with a fiber laser of 300 W maximum power (laser wavelength = 1060 nm, spot size = 70 µm) was used for D-PBSLP of SiC samples. SiC samples with a size of 10 × 10 × 8 mm 3 were printed to study the effect of the scanning strategies on the D-PBSLP of SiC, while samples of 10 × 10 × 4 mm 3 were printed for sintering speed investigation. Different scanning strategies available in the Phoenix 3D printer, such as concentric in-out, hexagonal, linear, and zigzag (Figure 7), were investigated in this study. The zigzag strategy is inclined with 45 • . The hexagon size used in the hexagonal strategy is 700 µm, and the scanning pattern inside the hexagon is inclined in a zigzag manner at 45 • and repeats randomly until scanning the powder layer. Argon inert gas was used to prevent the oxidation of the powder during the printing process. It is worth mentioning that the commercial Phoenix 3D printer is equipped with a system for powder layer compaction, and 100% compaction was used for all samples. Different characterization methods such as relative density measurements, 3D microscopic analysis, SEM imaging, and XRD analysis were used for the evaluation of the printed samples. Relative density was measured by the Archimedes method. The quality of the sample surfaces was checked using a 3D microscope (LEICA DM 4000 M). Bruker D8 was used for XRD analysis and JEOL JEM 6060 LV was used for SEM images.

Results and Discussion

Model Validation

To confirm and validate that the results obtained by the numerical model, the model was compared with the available data acquired by Zhang et al. [START_REF] Zhang | Simulation of The Thermal Behavior and Analysis of Solidification Process During Selective Laser Melting of Alumina[END_REF]. There is a good agreement between the two results, with a maximum error of 3.34%. Additionally, in order to re-confirm the model validation, the temperature contour obtained from the numerical model (Figure 8b) with the same conditions reported in [START_REF] Moser | Multi-Layer Computational Modeling of Selective Laser Sintering Processes[END_REF][START_REF] Wiria | Modeling of Powder Particle Heat Transfer Process in Selective Laser Sintering for Fabricating Tissue Engineering Scaffolds[END_REF] and the temperature contour captured using a thermal camera [START_REF] Moser | Multi-Layer Computational Modeling of Selective Laser Sintering Processes[END_REF][START_REF] Wiria | Modeling of Powder Particle Heat Transfer Process in Selective Laser Sintering for Fabricating Tissue Engineering Scaffolds[END_REF] confirm a good agreement with a calculation error of 1.24 % (Figure 8a). [START_REF] Montón | Experimental and Numerical Study for Direct Powder Bed Selective Laser Processing (Sintering/Melting) of Silicon Carbide Ceramic[END_REF] obtained using the same conditions used in [START_REF] Moser | Multi-Layer Computational Modeling of Selective Laser Sintering Processes[END_REF][START_REF] Wiria | Modeling of Powder Particle Heat Transfer Process in Selective Laser Sintering for Fabricating Tissue Engineering Scaffolds[END_REF].

Numerical Results

The laser power and sintering speed are essential parameters in the PBSLP of SiC. Using a low laser power with high sintering speed may lead to un-sintered powder particles, and using a high laser power with low sintering speed may lead to the decomposition of SiC and build failure. Therefore, using suitable laser power values and sintering speed is the key factor for successful D-PBSLP of SiC. The developed model was used to determine the suitable laser power values for different sintering speeds of 500, 250, and 100 mm/s using 22 µm layer thickness. The recommended laser power values were selected based on achieving full sintering of the layer thickness and adhering it with the layer below. Additionally, the predicted laser power should give a maximum temperature below the decomposition point of SiC. SiC starts to decompose when the temperature exceeds 2800 • C to form liquid silicon and carbon [START_REF] Meyers | Additive Manufacturing of Technical Ceramics: Laser Sintering of Alumina and Silicon Carbide[END_REF]. Therefore, it is recommended to keep the maximum temperature during PBSLP below the decomposition point of SiC. For sintering speeds of 500 mm/s, it was found that using a laser power of 15% (45 W) of the printer, maximum power (300 W) was able to sinter the layer thickness, but without adhering it to the layer below. Increasing the laser power to 20% (60 W) was found to sinter the layer thickness, adhere it to the baseplate and give a maximum temperature distribution below the decomposition point of SiC, as can be seen in Table 3. Therefore, it is recommended to use a laser power of 20% (60 W) with 500 mm/s sintering speed. The same procedure was followed with other sintering speeds, and the recommended laser power values are summarized in Table 4. Figure 9 gives the laser power range for different scanning speeds of 500, 250, and 100 mm/s. Hatching distance is another critical parameter that controls the contact between adjacent paths. Using a high hatching distance value leads to unconnected scanning paths that affect the printed part's mechanical properties. Additionally, small hatching distance values increase the building time and heat accumulated inside the part during the building. Therefore, it is crucial to use a suitable hatching distance value. The developed model was used to predict the hatching distance value by calculating the sintering path width for each scanning speed with the recommended laser power. The hatching distance Hatching distance is another critical parameter that controls the contact between adjacent paths. Using a high hatching distance value leads to unconnected scanning paths that affect the printed part's mechanical properties. Additionally, small hatching distance values increase the building time and heat accumulated inside the part during the building. Therefore, it is crucial to use a suitable hatching distance value. The developed model was used to predict the hatching distance value by calculating the sintering path width for each scanning speed with the recommended laser power. The hatching distance should be less than the scanning path width to connect the adjacent paths. Table 5 summarizes the width of the scanning path for each sintering speed with the laser power, according to the results obtained in Tables 3 and4. The sintering path widths were 38, 43, and 48 µm for 500, 250, and 100 mm/s sintering speeds, respectively. It can be noted that using a low sintering speed led to an increased sintering path width as the interaction time between the laser and the powder increased and, therefore, more particles were sintered. In order to connect the adjacent sintering paths together, it is recommended to select the hatching distance to be 35 µm (half the laser spot size) for all the sintering speeds.

Experimental Results

As described previously, this study investigates the effect of scanning strategies on the D-PBSLP of SiC and shows the best scanning strategy to be used. Four SiC samples (10 × 10 × 8 mm 3 ) were printed using the parameters obtained from the numerical model (100 mm/s scanning speed, 32 W laser power, 35 µm hatching distance, 22 µm layer thickness, and with different scanning strategies such as linear, zigzag, concentric in-out, and hexagonal), as can be seen in Figure 10. The samples were successfully printed using the parameters obtained from the numerical model, and this proved the capability of the numerical model to predict the suitable process parameters even for materials that are difficult to print using a D-PBSLP technique, such as SiC. It is worth mentioning that there is a breakage at the corner of the sample printed using linear strategy, and this happened

Experimental Results

As described previously, this study investigates the effect of scanning strategies on the D-PBSLP of SiC and shows the best scanning strategy to be used. Four SiC samples (10 × 10 × 8 mm 3 ) were printed using the parameters obtained from the numerical model (100 mm/s scanning speed, 32 W laser power, 35 µm hatching distance, 22 µm layer thickness, and with different scanning strategies such as linear, zigzag, concentric in-out, and hexagonal), as can be seen in Figure 10. The samples were successfully printed using the parameters obtained from the numerical model, and this proved the capability of the numerical model to predict the suitable process parameters even for materials that are difficult to print using a D-PBSLP technique, such as SiC. It is worth mentioning that there is a breakage at the corner of the sample printed using linear strategy, and this happened

Experimental Results

As described previously, this study investigates the effect of scanning strategies on the D-PBSLP of SiC and shows the best scanning strategy to be used. Four SiC samples (10 × 10 × 8 mm 3 ) were printed using the parameters obtained from the numerical model (100 mm/s scanning speed, 32 W laser power, 35 µm hatching distance, 22 µm layer thickness, and with different scanning strategies such as linear, zigzag, concentric in-out, and hexagonal), as can be seen in Figure 10. The samples were successfully printed using the parameters obtained from the numerical model, and this proved the capability of the numerical model to predict the suitable process parameters even for materials that are difficult to print using a D-PBSLP technique, such as SiC. It is worth mentioning that there is a breakage at the corner of the sample printed using linear strategy, and this happened 48

Experimental Results

As described previously, this study investigates the effect of scanning strategies on the D-PBSLP of SiC and shows the best scanning strategy to be used. Four SiC samples (10 × 10 × 8 mm 3 ) were printed using the parameters obtained from the numerical model (100 mm/s scanning speed, 32 W laser power, 35 µm hatching distance, 22 µm layer thickness, and with different scanning strategies such as linear, zigzag, concentric in-out, and hexagonal), as can be seen in Figure 10. The samples were successfully printed using the parameters obtained from the numerical model, and this proved the capability of the numerical model to predict the suitable process parameters even for materials that are difficult to print using a D-PBSLP technique, such as SiC. It is worth mentioning that there is a breakage at the corner of the sample printed using linear strategy, and this happened during the removal from the base plate as the samples were strongly attached to the baseplate. To evaluate the effect of scanning strategies on the D-PBSLP of SiC, all samples' relative densities were measured, and the results are summarized in Figure 11. Almost all scanning strategies gave a close relative density value. Both linear and concentric strategies obtained good relative density values of 76.6% and 79.9%, respectively. Zigzag and hexagonal strategies obtained the highest relative densities of 81.6% and 82.5%, respectively. Optical microscopic analysis was used to check the top surface of the samples, as shown in Figure 12. A flat surface without any characteristic pattern was achieved using zigzag and linear strategies. For the concentric in-out strategy, a characteristic pattern has appeared on the sample's top surface. This pattern is in two intersecting lines, which made an "X" shape on the layer's top surface. The developed numerical model was used to simulate two connected paths in this scanning strategy, and it was found that when the laser changed its direction, a sharp increase in temperature occurred, as can be seen in Figure 13. This sharp increase in temperature is high enough to decompose the material at the point of rotation. There are four points per cycle, and therefore, the X shapes were formed at the end of scanning. To avoid this pattern, a modification required for this scanning strategy. The hexagonal strategy also showed a characteristic pattern on the sample's top surface where the hexagon shapes can be seen. It can be concluded that these characteristic patterns that occurred in both concentric and hexagonal strategies make them ineffective for the D-PBSLP of SiC. Based on the measured relative density and the layer's top surface pattern, the zigzag strategy can be considered the best strategy for PBSLP of SiC. SEM images (Figure 14) were used to check the morphology for hexagonal, zigzag, and concentric in-out strategies on the sample's top surface. The sintered surface was observed in hexagonal and zigzag strategies without any characteristic pattern. The level of porosity can be clearly seen where it is high in the case of the concentric strategy and low for both the hexagonal and zigzag strategies. Additionally, in the concentric in-out strategy, laser tracks are apparent on the layer's top surface and the laser rotation positions. No cracks can be seen in any strategy. The linear sample was not checked using SEM due to the low relative density as the vacuum process required to start the SEM analysis failed many times. The X-ray diffraction spectrum of the SiC sample (Figure 15) produced by D-PBSLP using the zigzag strategy showed that SiC phases of silicon and carbon exist. This means that partial decomposition occurred, and this was expected due to the scanning strategies that generated high-temperature peaks during scanning when starting a new path. Figure 16 shows the temperature history (maximum temperature at the laser spot center) for the zigzag scanning strategy, where temperature peaks are clearly shown. These peaks can be eliminated by developing a new scanning strategy.

After investigating the scanning strategies' effects and seeing that the zigzag strategy shows a promising result for the direct SLS of SiC, SiC samples (10 × 10 × 4 mm 3 ) were printed with different sintering speeds and laser powers (as predicted from the numerical model), a 35 µm hatching distance and the zigzag strategy are shown in Figure 17. The samples were successfully printed using these parameters. However, it can be noted that the sample base has some deterioration, which is mainly due to its removal from the base plate. Additionally, the samples printed using 500 mm/s and 250 mm/s show layer degradation along the sample thickness. This is due to the low interaction time between the laser and the powder when using high scanning speeds. Relative density was used to evaluate the printed samples. A relative density of 84% was achieved for sample A, while 81% was achieved for samples B and C. After studying all the process parameter effects, trials for the printing of complex shapes were investigated. The triple periodic minimum surface (gyroid) was successfully printed using a laser power of 32 W, 100 mm/s scanning speed, 35 µm hatching distance, and the zigzag scanning strategy, as can be seen in Figure 18. The dimensions of the gyroid are (10 × 10 × 8 mm 3 ), which is a challenge to be printed using D-PBSLP, and this proves the power of the developed numerical model to obtain the proper process parameters.

Conclusions and Future Study

The scanning strategies' effects on the D-PBSLP of SiC were studied experimentally and numerically. Four scanning strategies, which are available in the commercial Phoenix 3D printer were considered in this study. These scanning strategies are concentric in-out, hexagonal, linear, and zigzag. The following points are concluded from this study:

1.

D-PBSLP OF SiC is possible through the optimization of the process parameters. 2.

The numerical model effectively predicts the process parameters even for hard to print materials such as SiC.

3.

For scanning strategies' effects, the concentric in-out and hexagonal strategies are ineffective in the D-PBSLP of SiC due to the characteristic pattern on the layer's top surface. Additionally, the linear strategy gave a low relative density value compared to other scanning strategies. 4.

The Zigzag strategy can be considered the best suitable strategy to be used with SiC, as it succeeds in giving a flat top surface without any characteristic pattern and a good relative density of more than 80%. Printing of SiC complex shapes using D-PBSLP was achieved using the proper process parameters obtained from the developed numerical model.

For future study, evaluating the mechanical properties should be covered.

Figure 1 .

 1 Figure 1. Schematic representation of the PBSLP process.

Figure 2 .

 2 Figure 2. The initial and boundary conditions used in the model. Additionally, the developed numerical model considered the SiC m as a function of temperature according to our previous study [34] on th 2.1.2. Model Geometry and the Computational Domain

Figure 2 .

 2 Figure 2. The initial and boundary conditions used in the model.

Figure 2 .

 2 Figure 2. The initial and boundary conditions used in the model.

Figure 3 .

 3 Figure 3. The model geometry used in the analysis (not to scale).

Figure 4 .

 4 Figure 4. Flowchart of the model solution procedure.

Figure 5 .

 5 Figure 5. The computational domain (the mesh) used in the analysis (not to scale).

Table 2 .Figure 5 .

 25 Figure 5. The computational domain (the mesh) used in the analysis (not to scale).

Figure 5 .

 5 Figure 5. The computational domain (the mesh) used in the analysis (not to scale).

Figure 5 .

 5 Figure 5. The computational domain (the mesh) used in the analysis (not to scale).

21 Figure 5 .

 215 Figure 5. The computational domain (the mesh) used in the analysis (not to scale).

4 * 2 ×

 42 Number of cores used in the calculation * 48 Elapsed time to solve one-step time (s) Intel ® Xeon ® Gold 6252 Processor (48 cores) is used for calculation with 96 Gb Ram.

Figure 6 .

 6 Figure 6. SEM of SiC powder [34].

Figure 7 .

 7 Figure 7. Scanning strategies used in this study: (a) Concentric in-out, (b) Hexagonal, (c) Linear and (d) Inclined Zigzag.

Figure 8 .

 8 Figure 8. (a) Numerical model validation with Zhang et al. [35], (b) Temperature contour[START_REF] Montón | Experimental and Numerical Study for Direct Powder Bed Selective Laser Processing (Sintering/Melting) of Silicon Carbide Ceramic[END_REF] obtained using the same conditions used in[START_REF] Moser | Multi-Layer Computational Modeling of Selective Laser Sintering Processes[END_REF][START_REF] Wiria | Modeling of Powder Particle Heat Transfer Process in Selective Laser Sintering for Fabricating Tissue Engineering Scaffolds[END_REF].

Figure 9 .

 9 Figure 9. Laser power range with sintering speeds of 500, 250, and 100 mm/s (layer thickness 22 µm).

Figure 9 .

 9 Figure 9. Laser power range with sintering speeds of 500, 250, and 100 mm/s (layer thickness 22 µm).

  . 2022, 12, x FOR PEER REVIEW 12 of 21

  Appl. Sci. 2022, 12, x FOR PEER REVIEW 12 of 21

Figure 10 .

 10 Figure 10. SiC samples printed using the process parameters obtained from the numerical model with different scanning strategies.

Figure 11 .

 11 Figure 11. Relative densities for SiC samples printed with different scanning strategies.

Figure 12 .

 12 Figure 12. Three-dimensional microscope images for SiC sample top surfaces printed using different scanning strategies.

Figure 13 .

 13 Figure[START_REF] Zocca | Additive Manufacturing of SiSiC by Layerwise Slurry Deposition and Binder Jetting (LSD-Print)[END_REF]. The peak occurring in the temperature history of the concentric in-out strategy when the laser source was changing its direction.

Figure 14 .

 14 Figure 14. Cont.

Figure 14 .

 14 Figure 14. SEM images for SiC samples printed using different scanning strategies.

Figure 15 .

 15 Figure 15. XRD spectra of the SiC powder and SiC manufactured part by D-PBSLP. (a) XRD spectra of the SiC powder; (b) XRD spectra of the SiC powder.

Figure 16 .

 16 Figure 16. Focused view for two scanning paths using the inclined zigzag strategy.

Figure 17 .

 17 Figure 17. SiC samples printed using laser power and sintering speed, as predicted from the numerical model, and zigzag scanning strategy.

Figure 18 .

 18 Figure 18. Triple periodic minimum surface (Gyroid) printed using the optimized process parameters.

Table 1 .

 1 Model dimensions.

	Parameter	Baseplate	Powder Layer
	Length (mm)	4	3
	Width (mm)	2.5	1.5
	Thickness (mm)	1	0.022
	2.1.3. Numerical solution

Table 2 .

 2 Discretization levels used in the analysis.

	Mesh	A	B	C
	Mesh
	Mesh element size (µm)
		5	2.5	2
	Number of cores used in the calculation *		48
	Elapsed time to solve one-step time (s)	3.92	6.89	8.4
	Temperature (K)	2343.7	2376.37	2379.4

* 2 × Intel ® Xeon ® Gold 6252 Processor (48 cores) is used for calculation with 96 Gb Ram.

Table 2 .

 2 Discretization levels used in the analysis.

	Mesh	A	B	C
	Mesh
	Mesh element size (µm)
		5	2.5	2
	Number of cores used in the calculation *		48
	Elapsed time to solve one-step time (s)	3.92	6.89	8.4
	Temperature (K)	2343.7	2376.37	2379.4

* 2 × Intel ® Xeon ® Gold 6252 Processor (48 cores) is used for calculation with 96 Gb Ram.

Table 2 .

 2 Discretization levels used in the analysis.

	Mesh	A	B	C
	Mesh
	Mesh element size (µm)
		5	2.5	2
	Number of cores used in the calculation *		48
	Elapsed time to solve one-step time (s)	3.92	6.89	8.4
	Temperature (K)	2343.7	2376.37	2379.4

* 2 × Intel ® Xeon ® Gold 6252 Processor (48 cores) is used for calculation with 96 Gb Ram.

Table 2 .

 2 Discretization levels used in the analysis.

	Mesh	A	B	C
	Mesh
	Mesh element size (µm)
		5	2.5	2
	Number of cores used in the calculation *		48
	Elapsed time to solve one-step time (s)	3.92	6.89	8.4
	Temperature (K)	2343.7	2376.37	2379.4

* 2 × Intel ® Xeon ® Gold 6252 Processor (48 cores) is used for calculation with 96 Gb Ram.

Table 3 .

 3 Laser power selection for sintering speed of 500 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour	Temperature Contour, K
	500	15% (45 W)

Appl. Sci. 2022, 12, x FOR PEER REVIEW 10 of 21

Table 3 .

 3 Laser power selection for sintering speed of 500 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour	Temperature Contour, K
	500	15% (45 W)
	500	20% (60 W)

Table 4 .

 4 Laser power selection for sintering speeds of 250 and 100 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour
	250	15% (45 W)

Appl. Sci. 2022, 12, x FOR PEER REVIEW 10 of 21

Table 3 .

 3 Laser power selection for sintering speed of 500 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour	Temperature Contour, K
	500	15% (45 W)
	500	20% (60 W)

Table 4 .

 4 Laser power selection for sintering speeds of 250 and 100 mm/s.

	500	20% (60 W)
	Sintering Speed, mm/s	Laser Power, W	Sintering Contour
	250		15% (45 W)

Appl. Sci. 2022, 12, x FOR PEER REVIEW 10 of 21

Table 3 .

 3 Laser power selection for sintering speed of 500 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour	Temperature Contour, K
	500	15% (45 W)
	500	20% (60 W)

Table 4 .

 4 Laser power selection for sintering speeds of 250 and 100 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour
	250	15% (45 W)

Appl. Sci. 2022, 12, x FOR PEER REVIEW 10 of 21

Table 3 .

 3 Laser power selection for sintering speed of 500 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour	Temperature Contour, K
	500	15% (45 W)
	500	20% (60 W)

Table 4 .

 4 Laser power selection for sintering speeds of 250 and 100 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour
	250	15% (45 W)

Table 4 .

 4 Laser power selection for sintering speeds of 250 and 100 mm/s.

	500	20% (60 W)
	Sintering Speed, mm/s	Laser Power, W	Sintering Contour
	250		15% (45 W)

Table 4 .

 4 Laser power selection for sintering speeds of 250 and 100 mm/s.

	Sintering Speed, mm/s	Laser Power, W	Sintering Contour
	250	15% (45 W)
	Appl. Sci. 2022, 12, x FOR PEER REVIEW	11 of 21
	100 100	11% (32 W) 11% (32 W)

Table 5 .

 5 The width of the scanning path for each sintering speed with the laser power.

	Appl. Sci. 2022, 12, x FOR PEER REVIEW		12 of 21
	Sintering Speed, mm/s	Laser Power, Wa	Sintering Contour	Sintering Path Width, µm
	500	60 W

Table 5 .

 5 The width of the scanning path for each sintering speed with the laser power.

	Sintering Speed, mm/s	Laser Power, Wa	Sintering Contour	Sintering Path Width, µm
	500	60 W		38
	250	45 W		43
	100	32 W		48

Table 5 .

 5 The width of the scanning path for each sintering speed with the laser power.

	Sintering Speed, mm/s	Laser Power, Wa	Sintering Contour	Sintering Path Width, µm
	500	60 W		38
	250	45 W		43
	100	32 W		48

Table 5 .

 5 The width of the scanning path for each sintering speed with the laser power.

	Sintering Speed, mm/s	Laser Power, Wa	Sintering Contour	Sintering Path Width, µm
	500	60 W		38
	250	45 W		43
	100	32 W		48

Funding: This project has received funding from the European Union's Framework Program for Research and Innovation Horizon 2020 (2014-2020) under the Marie Skłodowska-Curie Grant Agreement No. (764935).

Institutional Review Board Statement: Not applicable.

Informed Consent Statement:

The authors give the Publisher the permission to publish the work.

Conflicts of Interest:

The authors declare that they have no conflicts of interest/competing interests.


Mathias Weller
email: mathias.weller@cnrs.fr

Mathias Weller Neighbor

Joining Leaf

Neighbor Joining And Leaf Status

Keywords: Neighbor Joining, status in graphs, Phylogenetic Tree Reconstruction

diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction and Preliminaries

Neighbor Joining. Given n taxa, as well as pairwise distances1 d(u, v), the Neighbor Joining algorithm finds an undirected edge-weighted tree T whose leaves correspond to the n taxa and such that each two taxa u and v have distance d(u, v) in T , provided such a tree exists (the distances are called "additive" in this case). In this work, we call any such T a representation of the distances d. To find a representation for the input distances, the Neighbor Joining algorithm finds a pair of taxa that are guaranteed to form a cherry in some representation T of d. It then "merges" these two taxa into a new taxon corresponding to the mid-point of the cherry in T . Finally, the distances d are updated and a tree representing these new distances is found recursively. See [START_REF] Felsenstein | Inferring phylogenies[END_REF][START_REF] Swofford | Phylogenetic Inference[END_REF] for a more thorough explanation and examples for the Neighbor Joining algorithm.

A drawback of the algorithm is that finding a pair of taxa that form a cherry in a representation is a very opaque process, to the point where the technique has been called "obscure" or even "black magic" [START_REF] Compeau | Bioinformatics Algorithms: An Active Learning Approach -The Neighbor-Joining Algorithm[END_REF].

Efforts to render this important step more comprehensible and intuitive have been conducted [Att97; CHP93; Swo+96; VD91] (see the excellent collection by Bryant [START_REF] Bryant | On the uniqueness of the selection criterion in neighbor-joining[END_REF], indicating why each of them is not fully satisfying). Gascuel and Steel [START_REF] Gascuel | Neighbor-Joining Revealed[END_REF] concluded that "NJ greedily optimizes a natural tree length estimate" by selecting "at each step as neighbors that pair of current taxa, which most decreases the whole tree length, as computed using the generalized Pauplin formula". While this is a solid mathematical characterization, the "whole tree length" is hardly intuitive and proving that a pair that most decreases it should form a cherry in a representation of d is lengthy and tedious. Neighbor Joining will produce a tree even for non-additive distances and it has been claimed that the algorithm does not explicitly optimize any criterion in this case [START_REF] Felsenstein | Inferring phylogenies[END_REF][START_REF] Gascuel | Data model and classification by trees: the minimum variance reduction (MVR) method[END_REF][START_REF] Swofford | Phylogenetic Inference[END_REF].

In this work, we follow a similar path as Vach and Degens [START_REF] Vach | Least-squares approximation of additive trees to dissimilarities-characterizations and algorithms[END_REF], giving a simple and intuitive reformulation of the pair-selection criterion that allows easy verification of correctness for additive distances and hopefully helps teach this important algorithm in class. Indeed, it turns out that taxa u and v are selected to be merged if their hypothetical parent is furthest from the center of the representing tree, more precisely, it has maximum "leaf-status" (see below).

Let us have a closer look at the process of selecting taxa to be merged by the Neighbor Joining algorithm.

From the distances d(u, v), new quantities q(u, v) are computed as follows.

q(u, v) := (n -2) • d(u, v) - x d(u, x) - x d(v, x) (1)
Then, the pair (u, v) minimizing q(u, v) is selected to be merged. Correctness is established by Studier and Keppler [START_REF] Studier | A note on the neighbor-joining algorithm of Saitou and Nei[END_REF], who showed that this formulation is equivalent to the one used by Saitou and Nei [START_REF] Saitou | The neighbor-joining method: a new method for reconstructing phylogenetic trees[END_REF]. Indeed, leaves u and v minimizing q(u, v) form a cherry in the sought tree representing the distances d [Att97;

EL09].

Theorem 1 ("Neighbor Joining Theorem"). Let D be a distance matrix representable by a tree and let u and v be such that q(u, v), as defined in (1), is minimum. Then, there is a tree T representing D in which (u, v) is a cherry.

Trees, Status and Leaf-Status. Let T be an undirected tree. We denote its nodes by V(T ), its edges by E(T ) and its leaves (nodes with degree one) by L(T ). Two leaves u, v ∈ L(T ) are said to form a cherry in T if they are adjacent to the same node x and x is called the mid-point of the cherry. In this work, we will consider trees T that do not contain nodes of degree two. Let the edges of T be weighted by a function ω : E(T ) → N + . The distance d T (u, v) between nodes u, v ∈ V(T ) is the weight of the unique u-v-path in T . For a u-v-path p in T , we define the distance of a node x to p as the smallest distance of x to any node on p, that is, d T (x, p) := min u∈V(p) d(u, x).

Observation 1. Let u, v, x ∈ V(T ). The distance of x to the u-v-path p is d T (x, p) = 1 /2 (d(x, u) + d(x, v) -d(u, v)).
For any edge uv of T let L uv u denote the set of leaves x that are closer to u than to v in T , that is

L uv u := {x ∈ L(T ) | d T (x, u) < d T (x, v)}.
The status of u ∈ V(T ) in T is the sum of all distances from u, that is, s T (u) := x∈V(T ) d(u, x). While the status has been researched in the past [EJS76; Lin+12; LS09; QZ20; SL11], we require a slight variation of the concept: The leaf-status of u ∈ V(T ) in T is the sum of distances of u to all leaves, that is, ℓ T (u) := x∈L(T ) d(u, x). The leaf-status of a path p of T is the sum of distances of all leaves to p, that is, ℓ T (p) := x∈L(T ) d(x, p). With Observation 1, we observe that the leaf-status of a path can be formulated in terms of the leaf-statuses of its endpoints. Note how closely this formulation resembles Equation (1).

Observation 2. Let u, v ∈ V(T ) and let p be a u-v-path in T . Then, ℓ T (p) = 1 /2(ℓ T (u) + ℓ T (v) -|L(T )| • d(u, v)).
In the following, we will omit the subscript if T is clear from the context.

Working with Leaf-Statuses. As a warm-up, we prove a version2 of [EJS76, Property 2.2] for the leaf-status.

Lemma 1. Let uv ∈ E(T ). Then, ℓ(u) -ℓ(v) = ω(uv) |L uv v | -|L uv u | . Proof. ℓ(u) = a∈L uv u d(a, u) + b∈L uv v d(b, u) = a∈L uv u (d(a, u) + ω(uv) -ω(uv)) + b∈L uv v (d(b, u) -ω(uv) + ω(uv)) = a∈L uv u (d(a, v) -ω(uv)) + b∈L uv v (d(b, v) + ω(uv)) = ℓ(v) + ω(uv)(|L uv v | -|L uv u |)
Corollary 1. Let T be a tree with at least three leaves and let x ∈ V(T ) minimize ℓ(x). Then, x is not a leaf.

A central theorem concerning the status is that, for any path

(v 0 , v 1 , . . . , v k ) in T originating in a node v 0 of minimum status in T , we have s(v 0 ) ≤ s(v 1 ) < s(v 2 ) < . . . < s(v k ) [EJS76, Theorem 3.3].
Using Lemma 1, we show a similar version for the leaf-status of T even when edges are positively weighted.

Lemma 2. Let T be a tree with edge-weights ω : E(T ) → N + that is free of degree-2 nodes. Let (v 0 , v 1 , . . . , v k ) be a path in T and let v 0 have minimum leaf-status in T . Then, ℓ(v 0 ) ≤ ℓ(v 1 ) < ℓ(v 2 ) < . . . < ℓ(v t ).

Proof. For all i, we abbreviate

L ← i := L v i v i+1 v i
, that is, L ← i is the set of leaves that are closer to v i than to v i+1 , and L → i := L v i v i+1 v i+1 . Note that, as T is a tree without degree-2 nodes, we have

L ← i ⊂ L ← i+1 and L → i ⊃ L → i+1 , implying |L ← i | < |L ← i+1 | and |L → i | > |L → i+1 |. Further, for all i, as ω(v i v i+1 ) > 0, we have ℓ(v i ) ≤ ℓ(v i+1 ) Lemma 1 ⇐⇒ |L ← i | ≥ |L → i | and ℓ(v i ) = ℓ(v i+1 ) Lemma 1 ⇐⇒ |L ← i | = |L → i | (2)
We prove the lemma by induction on i.

For i = 0, ℓ(v i ) ≤ ℓ(v i+1 ) by definition of v 0 . Otherwise, ℓ(v i-1 ) ≤ ℓ(v i ) by induction hypothesis, implying |L ← i | > |L ← i-1 | ≥ |L → i-1 | > |L → i | by (2). But then, ℓ(v i ) < ℓ(v i+1 ) by (2).
Lemma 2 implies that, in analogy to the status, the nodes v minimizing the leaf-status are "in the center" of T and that ℓ(v) is a measure of "elongation from the center" of T .

Results

Instead of minimizing the "ominous" values q(u, v), we propose to maximize the leaf-status of the u-v-path p in the target tree T , augmented by the length d(u, v) of p:

z(u, v) := d(u, v) + ℓ(p) = d(u, v) + x∈L(T ) d(x, p) Observation 1 = d(u, v) + 1 /2 x∈L(T ) (d(u, x) + d(v, x) -d(u, v)) (3)
Indeed, q(u, v) = -2z(u, v) can be easily verified for all taxa u and v and, thus, maximizing z(u, v) is equivalent to minimizing q(u, v). The following key property connects z(u, v) to the leaf-status in a representation T for d.

Lemma 3. Let T be a tree with positive edge-weights without degree-2 nodes and let u, v ∈ L(T ). Let w be an inner node of the unique u-v-path p in T . Then, z(u, v) ≤ ℓ(w) and equality holds if and only if p = (u, w, v).

Proof. By definition, for all x ∈ L(T ), we have d(x, p) ≤ d(x, w) and, as T is free of degree-2 nodes and its edge-weights are positive, equality holds if and only if the x-w-path avoids all edges of p. Since d(u, v) = d(u, w) + d(w, v), we conclude z(u, v)

(3) = d(u, v) + x∈L(T ) d(x, p) = d(u, v) + x∈L(T )\{u,v} d(x, p) ≤ d(u, w) + d(v, w) + x∈L(T )\{u,v} d(x, w) = x∈L(T ) d(x, w) = ℓ(w),
and equality holds if and only if all paths from leaves x ∈ L(T )\{u, v} to w are edge-disjoint to p or, equivalently, all edges in p are incident with either u or v, that is, p = (u, w, v).

As the main contribution, the following theorem establishes the connection of z(u, v) to the leaf-status, thereby giving a simple, intuitive explanation of the correctness of the Neighbor Joining algorithm: it merges leaves u and v that, in each representation T for d, form a cherry whose mid-point has maximum leaf-status and, by Lemma 2, maximum elongation from the center of T .

Theorem 2. Let d be distances for at least three taxa, representable by a tree T and let u, v ∈ L(T ) such that z(u, v) is maximum. Then, u and v form a cherry in T and ℓ(w) = z(u, v) for its mid-point w.

Proof. Assume towards a contradiction that u and v do not form a cherry in T . Let c be a node of minimum leaf-status in T and let p be the unique c-u-path in T . By Corollary 1, c is not a leaf and the predecessor x of u in p is not a leaf either. By Lemma 3 and the assumption that u and v are not a cherry, z(u, v) < ℓ(x). Since x does not have degree two in T , we know that x has distinct neighbors s and t, none of which is u or v. Without loss of generality, let ℓ(s) ≥ ℓ(t). If s is a leaf in T , then z(u, s) = ℓ(x) > z(u, v) by Lemma 3, contradicting maximality of z(u, v). Thus, suppose that s is not a leaf in T . Clearly, Lemma 2 forbids ℓ(s), ℓ(t) ≤ ℓ(x) and, thus, ℓ(s) > ℓ(x). Of the two connected components of the result of removing the edge xs from T , let T s be the one containing s. Note that (a) u, c V(T s ) and (b) ℓ(y) > ℓ(x) for all y ∈ V(T s ) by Lemma 2. Since s is not a leaf in T , there is a cherry in T s that is also a cherry in T and, by Lemma 3, this cherry contradicts maximality of z(u, v). Thus, u and v form a cherry in T and, by Lemma 3, ℓ(x) = z(u, v).

Conclusion and Discussion

We presented a new, intuitive point of view onto the well-known Neighbor Joining algorithm. We show that finding the minimum in a matrix of "obscure" entries can be interpreted as finding the internal node w maximizing the "leaf-status", that is, the sum of distances to w in the target tree T . While the proof of the Neighbor Joining Theorem is usually skipped in class due to its complexity, our simplified explanation and proof can be taught to undergraduate students with reasonable effort.

The proof that we present here relies on the edge-weights in the target tree T being positive. Indeed, upon closer inspection, the proof only requires the edge-weights of all internal edges of T to be positive. Thus, our results are applicable to a modification of the Neighbor Joining algorithm that constructs the result of contracting all weight-zero edges between internal nodes of T . One can realize that, in presence of zero-weight internal edges in T , the Neighbor Joining algorithm returns an arbitrary binary tree T ′ such that contracting all zero-weight internal edges in T and in T ′ results in the same tree.

The distances between taxa can be obtained in a variety of ways, for example by comparing their genomes.

The original property is proved for the status in unweighted graphs, while ours is for the leaf-status in edge-weighted trees.

Funding

The author received no external funding.

Conflict of Interest Disclosure

The author declares no conflict of interest.

Data, script, code, and supplementary information availability

Not applicable.