Skip to content

Tracing Functions Modules

Miscellaneous tracing functions.

genTracingFuncs

Class of tracing functions.

Source code in topostats\tracing\tracingfuncs.py 
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
class genTracingFuncs:
    """Class of tracing functions."""

    @staticmethod
    def count_and_get_neighbours(x: int, y: int, trace_coordinates: list) -> tuple[int, list]:
        """
        Count the number of neighbouring points for a coordinate and an array containing those points.

        Parameters
        ----------
        x : int
            X coordinate.
        y : int
            Y coordinate.
        trace_coordinates : list
            Coordinates of the trace.

        Returns
        -------
        tuple
            The number of neighbours and the coordinates of the neighbouring points.
        """

        neighbour_array = []
        number_of_neighbours = 0
        if [x, y + 1] in trace_coordinates:
            neighbour_array.append([x, y + 1])
            number_of_neighbours += 1
        if [x + 1, y + 1] in trace_coordinates:
            neighbour_array.append([x + 1, y + 1])
            number_of_neighbours += 1
        if [x + 1, y] in trace_coordinates:
            neighbour_array.append([x + 1, y])
            number_of_neighbours += 1
        if [x + 1, y - 1] in trace_coordinates:
            neighbour_array.append([x + 1, y - 1])
            number_of_neighbours += 1
        if [x, y - 1] in trace_coordinates:
            neighbour_array.append([x, y - 1])
            number_of_neighbours += 1
        if [x - 1, y - 1] in trace_coordinates:
            neighbour_array.append([x - 1, y - 1])
            number_of_neighbours += 1
        if [x - 1, y] in trace_coordinates:
            neighbour_array.append([x - 1, y])
            number_of_neighbours += 1
        if [x - 1, y + 1] in trace_coordinates:
            neighbour_array.append([x - 1, y + 1])
            number_of_neighbours += 1
        return number_of_neighbours, neighbour_array

    @staticmethod
    def return_points_in_array(points_array: list | npt.NDArray, trace_coordinates: list | npt.NDArray) -> list:
        """
        Return a subset co ordinates for the given set of points.

        Parameters
        ----------
        points_array : list | npt.NDArray
            The subset of points for which coordinates are required.
        trace_coordinates : list | npt.NDArray
            Coordinates of all points.

        Returns
        -------
        list
            Coordinates for the subset of points.
        """
        for x, y in points_array:
            if [x, y] in trace_coordinates:
                try:
                    points_in_trace_coordinates.append([x, y])
                except NameError:
                    points_in_trace_coordinates = [[x, y]]
        # for x, y in points_array:
        #    print([x,y])
        #    try:
        #        trace_coordinates.index([x,y])
        #        print(trace_coordinates.index([x,y]))
        #    except ValueError:
        #        continue
        #    else:
        #        try:
        #            points_in_trace_coordinates.append([x,y])
        #        except NameError:
        #            points_in_trace_coordinates = [[x,y]]
        try:
            return points_in_trace_coordinates
        except UnboundLocalError:
            return None

    @staticmethod
    def make_grid(x: int, y: int, size: int) -> list:
        """
        Make a Grid of coordinates around the points x and y.

        Parameters
        ----------
        x : int
            The x coordinate.
        y : int
            They y coordinate.
        size : int
            Size of surrounding grid.

        Returns
        -------
        list
            List of coordinates that form a grid around x and y of size.
        """
        for x_n in range(-size, size + 1):
            x_2 = x + x_n
            for y_n in range(-size, size + 1):
                y_2 = y + y_n
                try:
                    grid.append([x_2, y_2])
                except NameError:
                    grid = [[x_2, y_2]]
        return grid

    @staticmethod
    def find_best_next_point(
        x: int, y: int, ordered_points: list | npt.NDArray, candidate_points: list | npt.NDArray
    ) -> list | None:
        """
        Find the next best point.

        Parameters
        ----------
        x : int
            The x coordinate.
        y : int
            They y coordinate.
        ordered_points : list | npt.NDArray
            Ordered points.
        candidate_points : list | npt.NDArray
            Points to be checked.

        Returns
        -------
        list
            Coordinates of the neighbouring pixel with the smallest angular change.
        """
        ordered_points = np.array(ordered_points)
        candidate_points = np.array(candidate_points)

        ordered_points = ordered_points.tolist()
        candidate_points = candidate_points.tolist()

        for i in range(1, 8):
            # build array of coordinates from which to check
            coords_to_check = genTracingFuncs.make_grid(x, y, i)
            # check for potential points in the larger search area
            points_in_array = genTracingFuncs.return_points_in_array(coords_to_check, candidate_points)

            # Make a decision depending on how many points are found
            if not points_in_array:
                continue
            elif len(points_in_array) == 1:
                best_next_point = points_in_array[0]
                return best_next_point
            else:
                best_next_point = genTracingFuncs.check_vectors_candidate_points(ordered_points, points_in_array)
                return best_next_point
        return None

    @staticmethod
    def check_vectors_candidate_points(
        ordered_points: list | npt.NDArray,
        candidate_points: list | npt.NDArray,
    ) -> list:
        """
        Find which neighbouring pixels incur the smallest angular change.

        This is done with reference to a previous pixel in the ordered trace, and chooses that as the next point.

        Parameters
        ----------
        ordered_points : list | npt.NDArray
            Ordered points.
        candidate_points : list | npt.NDArray
            Points to be checked.

        Returns
        -------
        list
            Coordinates of the neighbouring pixel with the smallest angular change.
        """
        x_test = ordered_points[-1][0]
        y_test = ordered_points[-1][1]

        if len(ordered_points) > 4:
            x_ref = ordered_points[-3][0]
            y_ref = ordered_points[-3][1]

            x_ref_2 = ordered_points[-2][0]
            y_ref_2 = ordered_points[-2][1]
        elif len(ordered_points) > 3:
            x_ref = ordered_points[-2][0]
            y_ref = ordered_points[-2][1]

            x_ref_2 = ordered_points[0][0]
            y_ref_2 = ordered_points[0][1]
        else:
            x_ref = ordered_points[0][0]
            y_ref = ordered_points[0][1]

            x_ref_2 = ordered_points[0][0]
            y_ref_2 = ordered_points[0][1]

        dx = x_test - x_ref
        dy = y_test - y_ref

        ref_theta = math.atan2(dx, dy)

        x_y_theta = []

        for x_n, y_n in candidate_points:
            x = x_n - x_ref_2
            y = y_n - y_ref_2

            theta = math.atan2(x, y)

            x_y_theta.append([x_n, y_n, abs(theta - ref_theta)])

        ordered_x_y_theta = sorted(x_y_theta, key=lambda x: x[2])
        return [ordered_x_y_theta[0][0], ordered_x_y_theta[0][1]]

check_vectors_candidate_points(ordered_points: list | npt.NDArray, candidate_points: list | npt.NDArray) -> list staticmethod

Find which neighbouring pixels incur the smallest angular change.

This is done with reference to a previous pixel in the ordered trace, and chooses that as the next point.

Parameters:

Name Type Description Default
ordered_points list | NDArray

Ordered points.

 required
candidate_points list | NDArray

Points to be checked.

 required

Returns:

Type Description
list

Coordinates of the neighbouring pixel with the smallest angular change.
Source code in topostats\tracing\tracingfuncs.py 
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
@staticmethod
def check_vectors_candidate_points(
    ordered_points: list | npt.NDArray,
    candidate_points: list | npt.NDArray,
) -> list:
    """
    Find which neighbouring pixels incur the smallest angular change.

    This is done with reference to a previous pixel in the ordered trace, and chooses that as the next point.

    Parameters
    ----------
    ordered_points : list | npt.NDArray
        Ordered points.
    candidate_points : list | npt.NDArray
        Points to be checked.

    Returns
    -------
    list
        Coordinates of the neighbouring pixel with the smallest angular change.
    """
    x_test = ordered_points[-1][0]
    y_test = ordered_points[-1][1]

    if len(ordered_points) > 4:
        x_ref = ordered_points[-3][0]
        y_ref = ordered_points[-3][1]

        x_ref_2 = ordered_points[-2][0]
        y_ref_2 = ordered_points[-2][1]
    elif len(ordered_points) > 3:
        x_ref = ordered_points[-2][0]
        y_ref = ordered_points[-2][1]

        x_ref_2 = ordered_points[0][0]
        y_ref_2 = ordered_points[0][1]
    else:
        x_ref = ordered_points[0][0]
        y_ref = ordered_points[0][1]

        x_ref_2 = ordered_points[0][0]
        y_ref_2 = ordered_points[0][1]

    dx = x_test - x_ref
    dy = y_test - y_ref

    ref_theta = math.atan2(dx, dy)

    x_y_theta = []

    for x_n, y_n in candidate_points:
        x = x_n - x_ref_2
        y = y_n - y_ref_2

        theta = math.atan2(x, y)

        x_y_theta.append([x_n, y_n, abs(theta - ref_theta)])

    ordered_x_y_theta = sorted(x_y_theta, key=lambda x: x[2])
    return [ordered_x_y_theta[0][0], ordered_x_y_theta[0][1]]

count_and_get_neighbours(x: int, y: int, trace_coordinates: list) -> tuple[int, list] staticmethod

Count the number of neighbouring points for a coordinate and an array containing those points.

Parameters:

Name Type Description Default
x int

X coordinate.

 required
y int

Y coordinate.

 required
trace_coordinates list

Coordinates of the trace.

 required

Returns:

Type Description
tuple

The number of neighbours and the coordinates of the neighbouring points.
Source code in topostats\tracing\tracingfuncs.py 
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
@staticmethod
def count_and_get_neighbours(x: int, y: int, trace_coordinates: list) -> tuple[int, list]:
    """
    Count the number of neighbouring points for a coordinate and an array containing those points.

    Parameters
    ----------
    x : int
        X coordinate.
    y : int
        Y coordinate.
    trace_coordinates : list
        Coordinates of the trace.

    Returns
    -------
    tuple
        The number of neighbours and the coordinates of the neighbouring points.
    """

    neighbour_array = []
    number_of_neighbours = 0
    if [x, y + 1] in trace_coordinates:
        neighbour_array.append([x, y + 1])
        number_of_neighbours += 1
    if [x + 1, y + 1] in trace_coordinates:
        neighbour_array.append([x + 1, y + 1])
        number_of_neighbours += 1
    if [x + 1, y] in trace_coordinates:
        neighbour_array.append([x + 1, y])
        number_of_neighbours += 1
    if [x + 1, y - 1] in trace_coordinates:
        neighbour_array.append([x + 1, y - 1])
        number_of_neighbours += 1
    if [x, y - 1] in trace_coordinates:
        neighbour_array.append([x, y - 1])
        number_of_neighbours += 1
    if [x - 1, y - 1] in trace_coordinates:
        neighbour_array.append([x - 1, y - 1])
        number_of_neighbours += 1
    if [x - 1, y] in trace_coordinates:
        neighbour_array.append([x - 1, y])
        number_of_neighbours += 1
    if [x - 1, y + 1] in trace_coordinates:
        neighbour_array.append([x - 1, y + 1])
        number_of_neighbours += 1
    return number_of_neighbours, neighbour_array

find_best_next_point(x: int, y: int, ordered_points: list | npt.NDArray, candidate_points: list | npt.NDArray) -> list | None staticmethod

Find the next best point.

Parameters:

Name Type Description Default
x int

The x coordinate.

 required
y int

They y coordinate.

 required
ordered_points list | NDArray

Ordered points.

 required
candidate_points list | NDArray

Points to be checked.

 required

Returns:

Type Description
list

Coordinates of the neighbouring pixel with the smallest angular change.
Source code in topostats\tracing\tracingfuncs.py 
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
@staticmethod
def find_best_next_point(
    x: int, y: int, ordered_points: list | npt.NDArray, candidate_points: list | npt.NDArray
) -> list | None:
    """
    Find the next best point.

    Parameters
    ----------
    x : int
        The x coordinate.
    y : int
        They y coordinate.
    ordered_points : list | npt.NDArray
        Ordered points.
    candidate_points : list | npt.NDArray
        Points to be checked.

    Returns
    -------
    list
        Coordinates of the neighbouring pixel with the smallest angular change.
    """
    ordered_points = np.array(ordered_points)
    candidate_points = np.array(candidate_points)

    ordered_points = ordered_points.tolist()
    candidate_points = candidate_points.tolist()

    for i in range(1, 8):
        # build array of coordinates from which to check
        coords_to_check = genTracingFuncs.make_grid(x, y, i)
        # check for potential points in the larger search area
        points_in_array = genTracingFuncs.return_points_in_array(coords_to_check, candidate_points)

        # Make a decision depending on how many points are found
        if not points_in_array:
            continue
        elif len(points_in_array) == 1:
            best_next_point = points_in_array[0]
            return best_next_point
        else:
            best_next_point = genTracingFuncs.check_vectors_candidate_points(ordered_points, points_in_array)
            return best_next_point
    return None

make_grid(x: int, y: int, size: int) -> list staticmethod

Make a Grid of coordinates around the points x and y.

Parameters:

Name Type Description Default
x int

The x coordinate.

 required
y int

They y coordinate.

 required
size int

Size of surrounding grid.

 required

Returns:

Type Description
list

List of coordinates that form a grid around x and y of size.
Source code in topostats\tracing\tracingfuncs.py 
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
@staticmethod
def make_grid(x: int, y: int, size: int) -> list:
    """
    Make a Grid of coordinates around the points x and y.

    Parameters
    ----------
    x : int
        The x coordinate.
    y : int
        They y coordinate.
    size : int
        Size of surrounding grid.

    Returns
    -------
    list
        List of coordinates that form a grid around x and y of size.
    """
    for x_n in range(-size, size + 1):
        x_2 = x + x_n
        for y_n in range(-size, size + 1):
            y_2 = y + y_n
            try:
                grid.append([x_2, y_2])
            except NameError:
                grid = [[x_2, y_2]]
    return grid

return_points_in_array(points_array: list | npt.NDArray, trace_coordinates: list | npt.NDArray) -> list staticmethod

Return a subset co ordinates for the given set of points.

Parameters:

Name Type Description Default
points_array list | NDArray

The subset of points for which coordinates are required.

 required
trace_coordinates list | NDArray

Coordinates of all points.

 required

Returns:

Type Description
list

Coordinates for the subset of points.
Source code in topostats\tracing\tracingfuncs.py 
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
@staticmethod
def return_points_in_array(points_array: list | npt.NDArray, trace_coordinates: list | npt.NDArray) -> list:
    """
    Return a subset co ordinates for the given set of points.

    Parameters
    ----------
    points_array : list | npt.NDArray
        The subset of points for which coordinates are required.
    trace_coordinates : list | npt.NDArray
        Coordinates of all points.

    Returns
    -------
    list
        Coordinates for the subset of points.
    """
    for x, y in points_array:
        if [x, y] in trace_coordinates:
            try:
                points_in_trace_coordinates.append([x, y])
            except NameError:
                points_in_trace_coordinates = [[x, y]]
    # for x, y in points_array:
    #    print([x,y])
    #    try:
    #        trace_coordinates.index([x,y])
    #        print(trace_coordinates.index([x,y]))
    #    except ValueError:
    #        continue
    #    else:
    #        try:
    #            points_in_trace_coordinates.append([x,y])
    #        except NameError:
    #            points_in_trace_coordinates = [[x,y]]
    try:
        return points_in_trace_coordinates
    except UnboundLocalError:
        return None

reorderTrace

Class to aid the consecutive ordering of adjacent coordinates of a pixel grid.

Source code in topostats\tracing\tracingfuncs.py 
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
class reorderTrace:
    """
    Class to aid the consecutive ordering of adjacent coordinates of a pixel grid.
    """

    @staticmethod
    def linearTrace(trace_coordinates: list | npt.NDArray) -> npt.NDArray:
        """
        Function to order the points from a linear trace.

        This works by checking the local neighbours for a given pixel (starting at one of the ends). If this pixel has
        only one neighbour in the array of unordered points, this must be the next pixel in the trace -- and it
        is added to the ordered points trace and removed from the remaining_unordered_coords array.

        If there is more than one neighbouring pixel, a fairly simple function (check_vectors_candidate_points) finds which
        pixel incurs the smallest change in angle compared with the rest of the trace and chooses that as the next
        point.

        This process is repeated until all the points are placed in the ordered trace array or the other end point is
        reached.

        Parameters
        ----------
        trace_coordinates : list | npt.NDArray
            Unordered trace coordinates.

        Returns
        -------
        npt.NDArray
            An array of ordered coordinates from one end of a linear trace to the other.
        """

        try:
            trace_coordinates = trace_coordinates.tolist()
        except AttributeError:  # array is already a python list
            pass

        # Find one of the end points
        for i, (x, y) in enumerate(trace_coordinates):
            if genTracingFuncs.count_and_get_neighbours(x, y, trace_coordinates)[0] == 1:
                ordered_points = [[x, y]]
                trace_coordinates.pop(i)
                break

        remaining_unordered_coords = trace_coordinates[:]

        while remaining_unordered_coords:
            if len(ordered_points) > len(trace_coordinates):
                break

            x_n, y_n = ordered_points[-1]  # get the last point to be added to the array and find its neighbour

            no_of_neighbours, neighbour_array = genTracingFuncs.count_and_get_neighbours(
                x_n, y_n, remaining_unordered_coords
            )

            if (
                no_of_neighbours == 1
            ):  # if there's only one candidate - its the next point add it to array and delete from candidate points
                ordered_points.append(neighbour_array[0])
                remaining_unordered_coords.pop(remaining_unordered_coords.index(neighbour_array[0]))
                continue
            elif no_of_neighbours > 1:
                best_next_pixel = genTracingFuncs.check_vectors_candidate_points(ordered_points, neighbour_array)
                ordered_points.append(best_next_pixel)
                remaining_unordered_coords.pop(remaining_unordered_coords.index(best_next_pixel))
                continue
            elif no_of_neighbours == 0:
                # nn, neighbour_array_all_coords = genTracingFuncs.count_and_get_neighbours(x_n, y_n, trace_coordinates)
                # best_next_pixel = genTracingFuncs.check_vectors_candidate_points(ordered_points, neighbour_array_all_coords)
                best_next_pixel = genTracingFuncs.find_best_next_point(
                    x_n, y_n, ordered_points, remaining_unordered_coords
                )

                if not best_next_pixel:
                    return np.array(ordered_points)

                ordered_points.append(best_next_pixel)

            # If the tracing has reached the other end of the trace then its finished
            if genTracingFuncs.count_and_get_neighbours(x_n, y_n, trace_coordinates)[0] == 1:
                break

        return np.array(ordered_points)

    @staticmethod
    def circularTrace(trace_coordinates):
        """
        Alternative implementation of the linear tracing algorithm but adapted to work with circular DNA molecules.

        Parameters
        ----------
        trace_coordinates : list | npt.NDArray
            Unordered trace coordinates.

        Returns
        -------
        npt.NDArray
            An array of ordered coordinates from one end of a linear trace to the other.
        """

        try:
            trace_coordinates = trace_coordinates.tolist()
        except AttributeError:  # array is already a python list
            pass

        remaining_unordered_coords = trace_coordinates[:]

        # Find a sensible point to start of the end points
        for i, (x, y) in enumerate(trace_coordinates):
            if genTracingFuncs.count_and_get_neighbours(x, y, trace_coordinates)[0] == 2:
                ordered_points = [[x, y]]
                remaining_unordered_coords.pop(i)
                break

        # Randomly choose one of the neighbouring points as the next point
        x_n = ordered_points[0][0]
        y_n = ordered_points[0][1]
        no_of_neighbours, neighbour_array = genTracingFuncs.count_and_get_neighbours(
            x_n, y_n, remaining_unordered_coords
        )
        ordered_points.append(neighbour_array[0])
        remaining_unordered_coords.pop(remaining_unordered_coords.index(neighbour_array[0]))

        count = 0

        while remaining_unordered_coords:
            x_n, y_n = ordered_points[-1]  # get the last point to be added to the array and find its neighbour

            no_of_neighbours, neighbour_array = genTracingFuncs.count_and_get_neighbours(
                x_n, y_n, remaining_unordered_coords
            )

            if (
                no_of_neighbours == 1
            ):  # if there's only one candidate - its the next point add it to array and delete from candidate points
                ordered_points.append(neighbour_array[0])
                remaining_unordered_coords.pop(remaining_unordered_coords.index(neighbour_array[0]))
                continue

            elif no_of_neighbours > 1:
                best_next_pixel = genTracingFuncs.check_vectors_candidate_points(ordered_points, neighbour_array)
                ordered_points.append(best_next_pixel)
                remaining_unordered_coords.pop(remaining_unordered_coords.index(best_next_pixel))
                continue

            elif len(ordered_points) > len(trace_coordinates):
                vector_start_end = abs(
                    math.hypot(
                        ordered_points[0][0] - ordered_points[-1][0], ordered_points[0][1] - ordered_points[-1][1]
                    )
                )
                if vector_start_end > 5:  # Checks if trace has basically finished i.e. is close to where it started
                    ordered_points.pop(-1)
                    return np.array(ordered_points), False
                else:
                    break

            elif no_of_neighbours == 0:
                # Check if the tracing is finished
                nn, neighbour_array_all_coords = genTracingFuncs.count_and_get_neighbours(x_n, y_n, trace_coordinates)
                if ordered_points[0] in neighbour_array_all_coords:
                    break

                    # Checks for bug that happens when tracing messes up
                if ordered_points[-1] == ordered_points[-3]:
                    ordered_points = ordered_points[:-6]
                    return np.array(ordered_points), False

                # Maybe at a crossing with all neighbours deleted - this is crucially a point where errors often occur
                else:
                    # best_next_pixel = genTracingFuncs.check_vectors_candidate_points(ordered_points, remaining_unordered_coords)
                    best_next_pixel = genTracingFuncs.find_best_next_point(
                        x_n, y_n, ordered_points, remaining_unordered_coords
                    )

                    if not best_next_pixel:
                        return np.array(ordered_points), False

                    vector_to_new_point = abs(math.hypot(best_next_pixel[0] - x_n, best_next_pixel[1] - y_n))

                    if vector_to_new_point > 5:  # arbitrary distinction but mostly valid probably
                        return np.array(ordered_points), False
                    else:
                        ordered_points.append(best_next_pixel)
                    if ordered_points[-1] == ordered_points[-3] and ordered_points[-3] == ordered_points[-5]:
                        ordered_points = ordered_points[:-6]
                        return np.array(ordered_points), False
                    continue

        ordered_points.append(ordered_points[0])
        return np.array(ordered_points), True

circularTrace(trace_coordinates) staticmethod

Alternative implementation of the linear tracing algorithm but adapted to work with circular DNA molecules.

Parameters:

Name Type Description Default
trace_coordinates list | NDArray

Unordered trace coordinates.

 required

Returns:

Type Description
NDArray

An array of ordered coordinates from one end of a linear trace to the other.
Source code in topostats\tracing\tracingfuncs.py 
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
@staticmethod
def circularTrace(trace_coordinates):
    """
    Alternative implementation of the linear tracing algorithm but adapted to work with circular DNA molecules.

    Parameters
    ----------
    trace_coordinates : list | npt.NDArray
        Unordered trace coordinates.

    Returns
    -------
    npt.NDArray
        An array of ordered coordinates from one end of a linear trace to the other.
    """

    try:
        trace_coordinates = trace_coordinates.tolist()
    except AttributeError:  # array is already a python list
        pass

    remaining_unordered_coords = trace_coordinates[:]

    # Find a sensible point to start of the end points
    for i, (x, y) in enumerate(trace_coordinates):
        if genTracingFuncs.count_and_get_neighbours(x, y, trace_coordinates)[0] == 2:
            ordered_points = [[x, y]]
            remaining_unordered_coords.pop(i)
            break

    # Randomly choose one of the neighbouring points as the next point
    x_n = ordered_points[0][0]
    y_n = ordered_points[0][1]
    no_of_neighbours, neighbour_array = genTracingFuncs.count_and_get_neighbours(
        x_n, y_n, remaining_unordered_coords
    )
    ordered_points.append(neighbour_array[0])
    remaining_unordered_coords.pop(remaining_unordered_coords.index(neighbour_array[0]))

    count = 0

    while remaining_unordered_coords:
        x_n, y_n = ordered_points[-1]  # get the last point to be added to the array and find its neighbour

        no_of_neighbours, neighbour_array = genTracingFuncs.count_and_get_neighbours(
            x_n, y_n, remaining_unordered_coords
        )

        if (
            no_of_neighbours == 1
        ):  # if there's only one candidate - its the next point add it to array and delete from candidate points
            ordered_points.append(neighbour_array[0])
            remaining_unordered_coords.pop(remaining_unordered_coords.index(neighbour_array[0]))
            continue

        elif no_of_neighbours > 1:
            best_next_pixel = genTracingFuncs.check_vectors_candidate_points(ordered_points, neighbour_array)
            ordered_points.append(best_next_pixel)
            remaining_unordered_coords.pop(remaining_unordered_coords.index(best_next_pixel))
            continue

        elif len(ordered_points) > len(trace_coordinates):
            vector_start_end = abs(
                math.hypot(
                    ordered_points[0][0] - ordered_points[-1][0], ordered_points[0][1] - ordered_points[-1][1]
                )
            )
            if vector_start_end > 5:  # Checks if trace has basically finished i.e. is close to where it started
                ordered_points.pop(-1)
                return np.array(ordered_points), False
            else:
                break

        elif no_of_neighbours == 0:
            # Check if the tracing is finished
            nn, neighbour_array_all_coords = genTracingFuncs.count_and_get_neighbours(x_n, y_n, trace_coordinates)
            if ordered_points[0] in neighbour_array_all_coords:
                break

                # Checks for bug that happens when tracing messes up
            if ordered_points[-1] == ordered_points[-3]:
                ordered_points = ordered_points[:-6]
                return np.array(ordered_points), False

            # Maybe at a crossing with all neighbours deleted - this is crucially a point where errors often occur
            else:
                # best_next_pixel = genTracingFuncs.check_vectors_candidate_points(ordered_points, remaining_unordered_coords)
                best_next_pixel = genTracingFuncs.find_best_next_point(
                    x_n, y_n, ordered_points, remaining_unordered_coords
                )

                if not best_next_pixel:
                    return np.array(ordered_points), False

                vector_to_new_point = abs(math.hypot(best_next_pixel[0] - x_n, best_next_pixel[1] - y_n))

                if vector_to_new_point > 5:  # arbitrary distinction but mostly valid probably
                    return np.array(ordered_points), False
                else:
                    ordered_points.append(best_next_pixel)
                if ordered_points[-1] == ordered_points[-3] and ordered_points[-3] == ordered_points[-5]:
                    ordered_points = ordered_points[:-6]
                    return np.array(ordered_points), False
                continue

    ordered_points.append(ordered_points[0])
    return np.array(ordered_points), True

linearTrace(trace_coordinates: list | npt.NDArray) -> npt.NDArray staticmethod

Function to order the points from a linear trace.

This works by checking the local neighbours for a given pixel (starting at one of the ends). If this pixel has only one neighbour in the array of unordered points, this must be the next pixel in the trace -- and it is added to the ordered points trace and removed from the remaining_unordered_coords array.

If there is more than one neighbouring pixel, a fairly simple function (check_vectors_candidate_points) finds which pixel incurs the smallest change in angle compared with the rest of the trace and chooses that as the next point.

This process is repeated until all the points are placed in the ordered trace array or the other end point is reached.

Parameters:

Name Type Description Default
trace_coordinates list | NDArray

Unordered trace coordinates.

 required

Returns:

Type Description
NDArray

An array of ordered coordinates from one end of a linear trace to the other.
Source code in topostats\tracing\tracingfuncs.py 
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
@staticmethod
def linearTrace(trace_coordinates: list | npt.NDArray) -> npt.NDArray:
    """
    Function to order the points from a linear trace.

    This works by checking the local neighbours for a given pixel (starting at one of the ends). If this pixel has
    only one neighbour in the array of unordered points, this must be the next pixel in the trace -- and it
    is added to the ordered points trace and removed from the remaining_unordered_coords array.

    If there is more than one neighbouring pixel, a fairly simple function (check_vectors_candidate_points) finds which
    pixel incurs the smallest change in angle compared with the rest of the trace and chooses that as the next
    point.

    This process is repeated until all the points are placed in the ordered trace array or the other end point is
    reached.

    Parameters
    ----------
    trace_coordinates : list | npt.NDArray
        Unordered trace coordinates.

    Returns
    -------
    npt.NDArray
        An array of ordered coordinates from one end of a linear trace to the other.
    """

    try:
        trace_coordinates = trace_coordinates.tolist()
    except AttributeError:  # array is already a python list
        pass

    # Find one of the end points
    for i, (x, y) in enumerate(trace_coordinates):
        if genTracingFuncs.count_and_get_neighbours(x, y, trace_coordinates)[0] == 1:
            ordered_points = [[x, y]]
            trace_coordinates.pop(i)
            break

    remaining_unordered_coords = trace_coordinates[:]

    while remaining_unordered_coords:
        if len(ordered_points) > len(trace_coordinates):
            break

        x_n, y_n = ordered_points[-1]  # get the last point to be added to the array and find its neighbour

        no_of_neighbours, neighbour_array = genTracingFuncs.count_and_get_neighbours(
            x_n, y_n, remaining_unordered_coords
        )

        if (
            no_of_neighbours == 1
        ):  # if there's only one candidate - its the next point add it to array and delete from candidate points
            ordered_points.append(neighbour_array[0])
            remaining_unordered_coords.pop(remaining_unordered_coords.index(neighbour_array[0]))
            continue
        elif no_of_neighbours > 1:
            best_next_pixel = genTracingFuncs.check_vectors_candidate_points(ordered_points, neighbour_array)
            ordered_points.append(best_next_pixel)
            remaining_unordered_coords.pop(remaining_unordered_coords.index(best_next_pixel))
            continue
        elif no_of_neighbours == 0:
            # nn, neighbour_array_all_coords = genTracingFuncs.count_and_get_neighbours(x_n, y_n, trace_coordinates)
            # best_next_pixel = genTracingFuncs.check_vectors_candidate_points(ordered_points, neighbour_array_all_coords)
            best_next_pixel = genTracingFuncs.find_best_next_point(
                x_n, y_n, ordered_points, remaining_unordered_coords
            )

            if not best_next_pixel:
                return np.array(ordered_points)

            ordered_points.append(best_next_pixel)

        # If the tracing has reached the other end of the trace then its finished
        if genTracingFuncs.count_and_get_neighbours(x_n, y_n, trace_coordinates)[0] == 1:
            break

    return np.array(ordered_points)

coord_dist(coords: npt.NDArray, pixel_to_nm_scaling: float = 1) -> npt.NDArray

Accumulate a real distance traversing from pixel to pixel from a list of coordinates.

Parameters:

Name Type Description Default
coords NDArray

A Nx2 integer array corresponding to the ordered coordinates of a binary trace.

 required
pixel_to_nm_scaling float

The pixel to nanometer scaling factor.

 1

Returns:

Type Description
NDArray

An array of length N containing thcumulative sum of the distances.
Source code in topostats\tracing\tracingfuncs.py 
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
def coord_dist(coords: npt.NDArray, pixel_to_nm_scaling: float = 1) -> npt.NDArray:
    """
    Accumulate a real distance traversing from pixel to pixel from a list of coordinates.

    Parameters
    ----------
    coords : npt.NDArray
        A Nx2 integer array corresponding to the ordered coordinates of a binary trace.
    pixel_to_nm_scaling : float
        The pixel to nanometer scaling factor.

    Returns
    -------
    npt.NDArray
        An array of length N containing thcumulative sum of the distances.
    """
    dist_list = [0]
    dist = 0
    for i in range(len(coords) - 1):
        if abs(coords[i] - coords[i + 1]).sum() == 2:
            dist += 2**0.5
        else:
            dist += 1
        dist_list.append(dist)
    return np.asarray(dist_list) * pixel_to_nm_scaling

local_area_sum(binary_map: npt.NDArray, point: list | tuple | npt.NDArray) -> npt.NDArray

Evaluate the local area around a point in a binary map.

Parameters:

Name Type Description Default
binary_map NDArray

A binary array of an image.

 required
point Union[list, tuple, NDArray]

A single object containing 2 integers relating to a point within the binary_map.

 required

Returns:

Type Description
NDArray

An array values of the local coordinates around the point.
int

A value corresponding to the number of neighbours around the point in the binary_map.
Source code in topostats\tracing\tracingfuncs.py 
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
def local_area_sum(binary_map: npt.NDArray, point: list | tuple | npt.NDArray) -> npt.NDArray:
    """
    Evaluate the local area around a point in a binary map.

    Parameters
    ----------
    binary_map : npt.NDArray
        A binary array of an image.
    point : Union[list, tuple, npt.NDArray]
        A single object containing 2 integers relating to a point within the binary_map.

    Returns
    -------
    npt.NDArray
        An array values of the local coordinates around the point.
    int
        A value corresponding to the number of neighbours around the point in the binary_map.
    """
    x, y = point
    local_pixels = binary_map[x - 1 : x + 2, y - 1 : y + 2].flatten()
    local_pixels[4] = 0  # ensure centre is 0
    return local_pixels, local_pixels.sum()

order_branch(binary_image: npt.NDArray, anchor: list)

Order a linear branch by identifying an endpoint, and looking at the local area of the point to find the next.

Parameters:

Name Type Description Default
binary_image NDArray

A binary image of a skeleton segment to order it's points.

 required
anchor list

A list of 2 integers representing the coordinate to order the branch from the endpoint closest to this.

 required

Returns:

Type Description
NDArray

An array of ordered coordinates.
Source code in topostats\tracing\tracingfuncs.py 
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
def order_branch(binary_image: npt.NDArray, anchor: list):
    """
    Order a linear branch by identifying an endpoint, and looking at the local area of the point to find the next.

    Parameters
    ----------
    binary_image : npt.NDArray
        A binary image of a skeleton segment to order it's points.
    anchor : list
        A list of 2 integers representing the coordinate to order the branch from the endpoint closest to this.

    Returns
    -------
    npt.NDArray
        An array of ordered coordinates.
    """
    skel = binary_image.copy()

    if len(np.argwhere(skel == 1)) < 3:  # if < 3 coords just return them
        return np.argwhere(skel == 1)

    # get branch starts
    endpoints_highlight = convolve_skeleton(skel)
    endpoints = np.argwhere(endpoints_highlight == 2)
    if len(endpoints) != 0:  # if any endpoints, start closest to anchor
        dist_vals = abs(endpoints - anchor).sum(axis=1)
        start = endpoints[np.argmin(dist_vals)]
    else:  # will be circular so pick the first coord (is this always the case?)
        start = np.argwhere(skel == 1)[0]
    # order the points according to what is nearby
    ordered = order_branch_from_start(skel, start)

    return np.array(ordered)

order_branch_from_start(nodeless: npt.NDArray, start: npt.NDArray, max_length: float | np.inf = np.inf) -> npt.NDArray

Order an unbranching skeleton from an end (startpoint) along a specified length.

Parameters:

Name Type Description Default
nodeless NDArray

A 2D array of a binary unbranching skeleton.

 required
start NDArray

2x1 coordinate that must exist in 'nodeless'.

 required
max_length float | inf

Maximum length to traverse along while ordering, by default np.inf.

 inf

Returns:

Type Description
NDArray

Ordered coordinates.
Source code in topostats\tracing\tracingfuncs.py 
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
def order_branch_from_start(
    nodeless: npt.NDArray, start: npt.NDArray, max_length: float | np.inf = np.inf
) -> npt.NDArray:
    """
    Order an unbranching skeleton from an end (startpoint) along a specified length.

    Parameters
    ----------
    nodeless : npt.NDArray
        A 2D array of a binary unbranching skeleton.
    start : npt.NDArray
        2x1 coordinate that must exist in 'nodeless'.
    max_length : float | np.inf, optional
        Maximum length to traverse along while ordering, by default np.inf.

    Returns
    -------
    npt.NDArray
        Ordered coordinates.
    """
    dist = 0
    # add starting point to ordered array
    ordered = []
    ordered.append(start)
    nodeless[start[0], start[1]] = 0  # remove from array

    # iterate to order the rest of the points
    current_point = ordered[-1]  # get last point
    area, _ = local_area_sum(nodeless, current_point)  # look at local area
    local_next_point = np.argwhere(
        area.reshape(
            (
                3,
                3,
            )
        )
        == 1
    ) - (1, 1)
    dist += np.sqrt(2) if abs(local_next_point).sum() > 1 else 1

    while len(local_next_point) != 0 and dist <= max_length:
        next_point = (current_point + local_next_point)[0]
        # find where to go next
        ordered.append(next_point)
        nodeless[next_point[0], next_point[1]] = 0  # set value to zero
        current_point = ordered[-1]  # get last point
        area, _ = local_area_sum(nodeless, current_point)  # look at local area
        local_next_point = np.argwhere(
            area.reshape(
                (
                    3,
                    3,
                )
            )
            == 1
        ) - (1, 1)
        dist += np.sqrt(2) if abs(local_next_point).sum() > 1 else 1

    return np.array(ordered)